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ť

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

Matěj Kripner

Člen

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ť

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ť

"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ť

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é

Odpovedať

Karel Vyborny

Člen

Karel Vyborny:4.5.2024 18:58

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

Odpovedať

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.

Zobrazené 6 správy z 6.

Najčastejšie vyhľadávané

Diskusia – Interpolačnou vyhľadávanie