Co to jest wyszukiwanie binarne?

Załóżmy, że dana osoba ma bardzo duży asortyment przedmiotów i układa je w uporządkowany sposób w długim rzędzie. Ta osoba może szybko dowiedzieć się, gdzie w wierszu znajduje się konkretny obiekt, korzystając z wyszukiwania binarnego. To wyszukiwanie odbywa się poprzez sprawdzenie środkowego elementu w rzędzie, a jeśli środkowy obiekt nie jest poszukiwanym przedmiotem, a następnie zajrzenie tylko do jednej z połówek rzędu, w której mógłby znajdować się przedmiot. Osoba wiedziałaby, w której połowie nadal szukać, ponieważ elementy są ułożone w kolejności. Te dwa kroki są wykonywane w kółko, na coraz mniejszych połówkach, dopóki przedmiot nie zostanie znaleziony lub nie będzie już gdzie szukać.

W dziedzinie informatyki wyszukiwanie binarne to procedura krok po kroku, która znajduje lokalizację lub indeks elementu w uporządkowanym po kolei zestawie danych. Dokonuje tego poprzez porównanie znanej wartości z wyznaczonym środkowym elementem tablicy i, jeśli nie jest równoważna, wielokrotnie ograniczając porównanie środkowego elementu do mniejszej odpowiedniej połowy zbioru, aż do uzyskania równoważności lub wyczerpania listy.

Wyszukiwanie binarne, czasami nazywane wyszukiwaniem z pół-interwałem, jest znacznie szybsze niż podstawowe wyszukiwanie sekwencyjne, które rozpoczyna się na jednym końcu listy elementów i porównuje każdy element po drodze, aż do znalezienia dopasowania lub do końca wyszukiwania Lista. Jeśli dana osoba miała 100 pozycji z rzędu, a ostatnia była poszukiwaną, sekwencyjne wyszukiwanie wymagałoby 100 porównań. Metoda bisekcji wymaga jednak najwyżej siedmiu porównań, zanim przedmiot zostanie znaleziony. Jest to oczywiście znacznie bardziej wydajne niż wyszukiwanie sekwencyjne.

Największą wadą wyszukiwania binarnego jest to, że lista elementów musi być posortowana, aby to wyszukiwanie działało. Sortowanie listy wymaga czasu. Sortowanie, a następnie wyszukiwanie tego typu może zająć więcej czasu niż wyszukiwanie innego typu.

Umiejętność korzystania z informacji, szczególnie z bardzo dużych zbiorów danych, jest ważna do wykonania wielu zadań w życiu. Dyscyplina informatyki zajmuje się wieloma rodzajami problemów, w tym znalezieniem skutecznych sposobów wyszukiwania informacji w celu uzyskania użytecznych wyników. Wyszukiwanie binarne jest tylko jednym z wielu dostępnych algorytmów do przeszukiwania danych.