[megoldva] Logaritmikus (bináris) keresés intervallumokra

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

Szerkesztve: 2020. 09. 08., k – 11:54

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