NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - 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
16.5.2016 11:48
"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"
Avatar
Matěj Kripner
Tvůrce
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.

 
Odpovědět
16.5.2016 17:49
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
17.5.2016 9:25
"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

 
Odpovědět
24.5.2019 8:42
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 23.4.2022 17:34
 
Odpovědět
23.4.2022 17:32
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"

 
Odpovědět
4.5.2024 18:58
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.