Bináris keresési algoritmusok magyarázata a C ++ használatával

A bináris keresés egyike azoknak az algoritmusoknak, amelyekkel minden (jó) bevezető informatika órán találkozhat. Ez egy hatékony algoritmus egy tétel megkeresésére egy rendezett listában. A példa kedvéért feltételezzük, hogy ez egy tömb.

A bináris keresés célja:

  • minden iterációnál el tudja dobni a tömb felét
  • minimalizálja az átmenő elemek számát
  • hagyjon nekünk egy végső értéket

Vegyük például a következő egész számtömböt:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Tegyük fel, hogy megpróbáljuk megtalálni a 7-es szám indexértékét ebben a tömbben. Összesen 17 elem van, és az indexértékek 0-tól 16-ig terjednek.

Láthatjuk, hogy a 7 index értéke 4, mivel ez a tömb ötödik eleme.

De mi lenne a legjobb módja annak, hogy a számítógép megtalálja a keresett szám indexértékét?

Először tároljuk az minés maxértékeket, például a 0és 16.

int min = 0;int max = 16;

Most ki kell találnunk egy találgatást. A legokosabb dolog lenne kitalálni egy indexértéket a tömb közepén.

Ha ebben a tömbben 0 és 16 közötti indexérték van, ennek a tömbnek a középső index értéke 8. Ez a 14. számot tartja.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Tippelésünk most egyenlő 8-mal, ami 14 a tömbben, mivel array[8]egyenlő 14.

Ha a keresett szám 14 lenne, akkor készen lennénk!

Mivel ez nem így van, most elvetjük a tömb felét. Ezek mind a 14 utáni számok, vagy a 8. indexérték, mivel tudjuk, hogy a 14 nagyobb, mint 7, és a tippünk túl magas.

Az első iteráció után a keresés a következő helyen van: 1, 3, 4, 6, 7, 8, 10, 13

Nem kell kitalálnunk az eredeti tömb utolsó felében, mert tudjuk, hogy ezek az értékek túl nagyok. Ezért fontos, hogy bináris keresést alkalmazzunk egy rendezett listára.

Mivel az eredeti 14-es tippünk nagyobb volt, mint 7, most 1-gyel csökkentjük, és ezt tároljuk max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Most a keresés így néz ki:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Mivel a találgatásunk túl alacsony volt, a tömb alsó felét elvetjük azzal, hogy növeljük az értéket min, ellentétben azzal, amit korábban tettünk max:

min = guess + 1; // min is now 4

A következő iterációra:

 7, 8, 10, 13min = 4max = 7guess = 5

Mivel az 5. index értéke 8-at ad vissza, most már túl vagyunk a célon. Ismételjük meg a folyamatot, és marad:

 7min = 4max = 4guess = 4

És csak egy értékünk marad, 4, mint a keresett célszám indexe, amely 7 volt.

A bináris keresés célja, hogy minden iterációnál megszabaduljon a tömb felétől. Tehát csak azokon az értékeken dolgozunk, amelyekről van értelme tovább találgatni.

Az algoritmus álkódja így néz ki:

  1. Hagyja min = 0, és hagyja, max = nahol na lehető legnagyobb indexérték van
  2. Keresse az átlagos minés a maxkerek le, így ez egy egész szám. Ez a miénkguess
  3. Ha kitaláltuk a számot, állj meg, megkaptuk!
  4. Ha guesstúl alacsony, állítsa be minaz eggyel többre, mintguess
  5. Ha guesstúl magas, állítsa be maxaz eggyel kevesebbet, mintguess
  6. Térjen vissza a második lépésre.

Itt van egy megoldás, C ++ nyelven írva: