Fórumok
Biztos feltalálták már azt a spanyolviaszt, ami a bináris keresésnek egy olyan válfaja, amikor nem pontos értéket keresünk, hanem csak azt, hogy melyik "résben" van a keresett érték. Azaz pl. melyik (legnagyobb) tömbelemnél nagyobb-egyenlő a keresett elem.
Pl.
[0] => 0
[1] => 0.02792
[2] => 0.05246
[3] => 0.09098
[4] => 0.126
[5] => 0.2
S itt szeretném elhelyezni mondjuk a 0.1-et, aminek 3 lenne a helyes megoldása.
Próbáltam magam is összehozni az algoritmust, de valahogy még nem szép – biztos nem nálam merült ez föl először. Mi ennek a feladatnak a hivatalos neve?
A saját megoldásom egyelőre ez:
function ge($element, $array)
{
$top = sizeof($array) -1;
$bot = 0;
while($top >= $bot) {
$p = (int)floor(($top + $bot) / 2);
if ($array[$p] < $element) $bot = $p + 1;
elseif ($array[$p] > $element) $top = $p - 1;
else return $p;
}
return $top;
Szerk: most látom, hogy a https://wiki.prog.hu/wiki/Logaritmikus_keresés_(algoritmus) végén az utolsó bekezdés épp ezt taglalja.
Hozzászólások
Elektronikában használtam ilyet. Egy MOSFET Id(Ugs) nonlineáris karakterisztikáján kerestem, adott Id-hez mekkora Ugs tartozik.
Úgy csináltam, hogy feleztem a jelenlegi alsó és felső határ által meghatározott intervallumot, majd megnéztem, az így kapott index értékkel milyen érték adódott, tehát amit keresünk, az alsó vagy a felső intervallumban van-e. Ha az alsóban, a felső indexet módosítottam a felezett indexre, ha a felsőben, úgy az alsó index mozgott a felezettre. Aztán következő iteráció. A végén kell figyelni, nehogy végtelen ciklus legyen, végig kell diszkutálni, hogy mikor jó a kisebb vagy egyenlő, esetleg nagyobb vagy egyenlő feltétel, mi van, ha az alsó és felső index közötti különbség 1-re csökkent, stb.
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
Ez a rendezett listán való bináris keresés.
Igen, es OP-nak pont ez kell.
A strange game. The only winning move is not to play. How about a nice game of chess?
Igen, a függvény monotonitása feltétel.
tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE
> Biztos feltalálták már azt a spanyolviaszt
Igen, feltalálták, standard libekben szokott lenni hasonló:
https://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html#tail…
https://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html#head…
A firstKey/lastKey-jel kombinálva hasonló funkcionalitást lehet ezzel elérni például.
https://www.geeksforgeeks.org/search-insert-and-delete-in-a-sorted-arra…
Továbbá: https://www.geeksforgeeks.org/binary-insertion-sort/