Binary search znajduje cel w posortowanej tablicy poprzez wielokrotne zmniejszanie zakresu wyszukiwania o połowę. Każde porównanie eliminuje połowę pozostałych elementów, co daje złożoność O(log n).
Idea
Spójrz na element środkowy. Jeśli jest równy celowi, gotowe. Jeśli cel jest mniejszy, przeszukaj lewą połowę; jeśli większy, przeszukaj prawą połowę. Powtarzaj, aż znajdziesz lub zakres będzie pusty.
