Wyszukiwanie binarne

Z Wikipedii

Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks.

[edytuj] Zasada działania algorytmu

Uporządkowaną tablicę dzielimy na coraz mniejsze kawałki (przedziały) do momentu, gdy znajdziemy szukany element bądź przedział będzie zerowej długości (brak elementu). Rozpoczynamy od pełnej tablicy, czyli lewy koniec przedziału ustawiamy na początek tablicy a prawy na koniec. Następnie "celujemy" w środek przedziału i odczytujemy wartość. Jeśli jest równa szukanemu elementowi to koniec, znaleźliśmy element, wpp. są możliwe dwa przypadki. Jeśli odczytana wartość jest większa od szukanej oraz tablica jest uporządkowana niemalejąco (odpowiednio malejąco), prawy (lewy) koniec przedziału ustawiamy na odczytaną wartość. W drugim przypadku - odczytana wartość mniejsza - postępujemy analogicznie, czyli: lewym (prawym) końcem przedziału staje się "środkowy" element. Algorytm wykonujemy tak długo, aż znajdziemy szukany element bądź lewy koniec "znajdzie się" za prawym końcem.

[edytuj] Przykładowy kod

Kod wyszukiwania binarnego w C++, dla tablicy uporządkowanej niemalejąco (→ sortowanie).

int szukaj(int *tab, int n, int x) {
/* parametry:
 * tab - wskaźnik na tablicę elementów
 * n   - liczba elementów w tablicy
 * x   - szukany element
 * zwracana wartość:
 * indeks elementu - jeśli znajduje się w tablicy
 * w przeciwnym wypadku zwraca -1
 */
  int pocz = -1, kon = n , srod = 0;    
 
  while (kon > pocz + 1) {
    srod = ( pocz + kon ) / 2;
    if (tab[srod] == x)  
      return(srod);
    else {
    if (tab[srod] < x)
      pocz = srod;
    else
      kon = srod;
    }
  }  
  return(-1);    
}

[edytuj] Zobacz też

• Metoda równego podziału