Diskusia – Interpolačnou vyhľadávanie

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

Michal Vlasák

Člen

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.

Odpovedať

16.5.2016 11:48

"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"

Matěj Kripner

Tvůrce

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.

Odpovedať

16.5.2016 17:49

Michal Vlasák

Člen

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>

Odpovedať

17.5.2016 9:25

"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"

Patrik Pastor

Člen

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

Odpovedať

24.5.2019 8:42

Dzhohar Isaev

Člen

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

Editované 23.4.2022 17:34

Odpovedať

23.4.2022 17:32

Karel Vyborny

Člen

Karel Vyborny:4. mája 18:58

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

Odpovedať

4. mája 18:58

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!