Mire használják a bináris keresést

Binary Search Master Theorem Dichotómia: bináris keresés A bináris keresés akkor megfelelő, ha nagy az adatmennyiség, de először az adatokat kell rendezni.

A fő gondolat: tegyük fel, hogy a keresett tömb intervalluma tömb [alacsony, magas] Határozza meg az intervallum K 2 középső helyzetét, és hasonlítsa össze a keresett T értéket a [k] tömbvel. Ha egyenlőek, akkor a keresés egyébként sikeresen visszatér ebbe a helyzetbe, új keresési területet határoz meg és folytatja a bináris keresést. A terület meghatározása a következőképpen történik: a.

Kör [k] Valahányszor a keresést összehasonlítják a köztes értékkel, meghatározható, hogy a keresés sikeres-e vagy sem, az aktuális keresési intervallum felére csökken, ha sikertelen, és a rekurzív keresés is elegendő. Az idő összetettsége: O log2n Egydimenziós tömb: Félkeresés] Ha van egy 3, 12, 24, 36, 55, 68, 75, 88 számok csoportja a megadott érték ellenőrzésére. Ez azt jelenti, hogy a keresés sikertelen.

Példa: Keresse meg a felhasználó által beírt x adatot N elem rendezett tömbjében. Az algoritmus a következő: 1.

Ha egy [közép] x, ez azt jelenti, hogy a keresendő elem értéke csak a középső elemnél kisebb tartományban lehet, akkor rendelje hozzá a közepe 1 értékét a végéig, számolja újra a közepét és folytassa a lépéssel 2.

A mester tételét a rekurzív algoritmus időbeli összetettségének gyors megszerzésére használják.

A számítás időbeli összetettsége általában O 1 Kategóriák.