Wyszukiwanie binarne

Jeden z wydawać by się mogło z prostszych algorytmów - przecież nie ma tu nic trudnego. Znalezienie środkowego elementu tablicy, porównanie go z tym wyszukiwanym i wykonanie tego samego kroku dla odpowiedniej pozostałej części tablicy. Nic trudnego?

Jon Bentley w "Perełkach oprogramowania" (1986) podkreśla, że o ile powyższy algorytm został opisany w druku w 1946r., to pierwsza wersja bez błędów ukazała się w 1962r. (bite 16 lat). Autor przy okazji wspomina, że kiedy na prowadzonym przez niego szkoleniu zadanie napisania wyszukiwania binarnego w ciągu paru godzin dostali zawodowi programiści, to 90% z nich skończyło z błędami.

Następnie w swojej książce Bentley opisuje prawidłową wersję algorytmu i na 30 stronach formalnie dowodzi jej poprawności oraz poprawności implementacji w C. W drugim wydaniu (2000) nie wprowadził żadnych zmian w swoim wyszukiwaniu binarnym.

W 2006r. został odnaleziony w nim błąd.

Implementacja Bentleya wyglądała mniej więcej tak (napisałem to w C++ z użyciem szablonów:

const int NOT_FOUND = -1;

template<class T>
int binary_search(T arr[], int len, T key)
{
  int d = 0;
  int u = len - 1;
  while (d <= u) {
    int m = (d + u) / 2; // uwaga!!!
    T mVal = arr[m];
    if (mVal < key) {
      d = m + 1;
    } else if (mVal > key) {
      u = m - 1;
    } else { // mVal == key
      return m;
    }
  }
  return NOT_FOUND;
}

Błąd kryje się w oznaczonej linii i jest błędem przepełnienia, który pojawić się może dla naprawdę dużych zestawów danych. Ciekawy jest sposób, w jaki został on odkryty.

Został on zgłoszony w 2006 roku do Sun Microsystems jako błąd biblioteki standardowej Javy. Był on obecny w Javie od ponad 9 lat, ale dopóki nie był wykorzystywany dla tablic większych niż miliard elementów pozostał nieodkryty.

Przy okazji nie zazdroszczę człowiekowi, który bezskutecznie szukał błędu w swoim programie, a znalazł go w bibliotece standardowej.

Poprawna implementacja:

const int NOT_FOUND = -1;

template<class T>
int binary_search(T arr[], int len, T key)
{
  int d = 0;
  int u = len - 1;
  while (d <= u) {
    int m = d + ((u - d)/2); // uwaga!!!
    T mVal = arr[m];
    if (mVal < key) {
      d = m + 1;
    } else if (mVal > key) {
      u = m - 1;
    } else { // mVal == key
      return m;
    }
  }
  return NOT_FOUND;
}

Więcej szczegółów: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html