POUZE NYNÍ: Získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjistit více.
NOVINKA: Staň se datovým analytikem od 0 Kč a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:

Diskuze – Lekce 4 - Interpolační vyhledávání

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
Avatar
Michal Vlasák
Člen
Avatar
Michal Vlasák:16.5.2016 11:48

Ahoj,
zajímavý článek. Chápu, že jsou kódy v rekonstrukci. Ale jestli jsem to pochopil dobře, tak interpolační vyhledávání se spíš hodí na textové řetězce, protože vzdálenosti jednotlivých prvků pro získání poměru mi pro čísla přijde zbytečné, tam bych asi volil klasické binární vyhledávání se středem.

Odpovědět
"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"
Avatar
Matěj Kripner
Člen
Avatar
Odpovídá na Michal Vlasák
Matěj Kripner:16.5.2016 17:49

Nejde o to, co řadíš - interpolační vyhledávání je obecný algoritmus. U čísel je to ale nejjednodušší - jejich "číselnou hodnotu" získáš prostým přečtením, na rozdíl od komplexnějších struktur - třeba řetězců, kde ji musíš obvykle počítat.

Avatar
Michal Vlasák
Člen
Avatar
Michal Vlasák:17.5.2016 9:25

Pro toho, koho zajímá PHP a vyhledávání řetězců, jsem kód přetvořil. Při automatickém převodu řetězce na číslo docházelo k varování division by zero, takže jsem přidal jednu podmínku.

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8" />
        <title>Interpolační vyhledávání</title>
    </head>
    <body>
        <?php
            function binary_search($array, $item){
                sort($array);
                print_r($array);

                $left = 0;
                $right = count($array) - 1;

                if(($item < $array[$left]) || ($item > $array[$right])){
                    return false;
                }
                while($left <= $right){
                    if($left == $right){
                        $candidate = $left;
                    }
                    /*při převodu textu na číslo docházelo k varování division by zero,
                     *tato podmínka to odstraňuje*/
                    elseif(($array[$right] - $array[$left]) == 0){
                        $candidate = $left;
                    }
                    else{
                        //X = L + (R - L) * (XX - LL) / (RR - LL)
                        $candidate = $left + ($right - $left) * ($item - $array[$left]) / ($array[$right] - $array[$left]);
                    }
                    if($item == $array[$candidate]){
                        settype($candidate, "integer");
                        return $candidate;
                    }
                    else{
                        if($item < $array[$candidate]){
                            $right = $candidate - 1;
                        }
                        else{
                            $left = $candidate + 1;
                        }
                    }
                }
            }

            $technics = array("Novák", "Malý", "Suchar", "Komínek", "Lukáš", "Levý");
            $searched = "Levý";

            $position = binary_search($technics, $searched);
            echo "<br />" . $searched . "  se nachází na pozici " . $position . ".<br />";
        ?>
    </body>
</html>
Odpovědět
"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"
Avatar
Patrik Pastor
Člen
Avatar
Odpovídá na Michal Vlasák
Patrik Pastor:24.5.2019 8:42

nemas tam jakoby 2 podminky pro deleni nulou? kdyz uz tam je (if $left == $right)

To ma prece zamezit aby byl ve jmenovateli rozdil nulty, cili uz tato podmika by mela zamezit divide by zero exception

Avatar
Dzhohar Isaev
Člen
Avatar
Dzhohar Isaev:23.4.2022 17:32

Ahoj, muzu se zeptat ohledne interpolacniho vyhledavani: jak se pocita ta vzdalenost pro String hodnoty? Vzdalenost Hamming a Levenshtein nefunguje :), predem dekuji

Editováno
Avatar
Karel Vyborny
Člen
Avatar
Karel Vyborny:4.5.2024 18:58

v C "array.length - 1" mělo by být "array.Length - 1"

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.