Co to jest wyszukiwanie binarne?

Załóżmy, że dana osoba ma bardzo duży asortyment przedmiotów i ułoży ją w pewien sposób w długim rzędzie.Ta osoba może szybko dowiedzieć się, gdzie w wierszu znajduje się konkretny obiekt za pomocą wyszukiwania binarnego.To wyszukiwanie odbywa się poprzez sprawdzanie środkowego elementu w wierszu, a jeśli środkowy obiekt nie jest poszukiwanym przedmiotem, a następnie patrząc tylko w jednej z połówki rzędu, w którym może być przedmiot.Osoba wiedziałaby, którą połowę nadal szukać, ponieważ elementy są ułożone w porządku.Te dwa kroki są wykonywane w kółko, na coraz mniejszych połówkach, dopóki przedmiot albo nie zostanie znaleziony, albo nie pozostanie nie do zobaczenia.

W dziedzinie informatyki wyszukiwanie binarne jest procedurą krok po kroku.Znajduje lokalizację lub indeks elementu w sekwencyjnie posortowanym zestawie danych.Osiąga to, porównując znaną wartość z wyznaczonym środkowym elementem tablicy, a jeśli nie jest równoważny, wielokrotnie ograniczając porównanie elementu środkowego z mniejszą istotną połową zestawu, aż do uzyskania równoważności lub wyczerpanie listy.

Wyszukiwanie binarne, czasami nazywane wyszukiwaniem półprodukcyjnym, jest znacznie szybsze niż podstawowe sekwencyjne wyszukiwanie, które rozpoczyna się na jednym końcu listy elementów i porównuje każdy element po drodze do znalezienia dopasowania lub do momentu, aż wyszukiwanie dotrze dokoniec listy.Gdyby dana osoba miała 100 elementów z rzędu, a ostatni element był tym, którego szukano, sekwencyjne wyszukiwanie przyjąłoby 100 porównań.Metoda bisekcji wymaga jednak tylko siedmiu porównań przed znalezieniem elementu.Jest oczywiście znacznie bardziej wydajny niż sekwencyjne wyszukiwanie.

Największą wadą wyszukiwania binarnego jest to, że lista elementów musi zostać posortowana, aby to wyszukiwanie działało.Sortowanie listy wymaga czasu.Następnie sortowanie tego rodzaju wyszukiwania może zająć więcej czasu niż przede wszystkim wykonanie innego rodzaju wyszukiwania.

Możliwość wykorzystywania informacji, szczególnie z bardzo dużych zestawów danych, jest ważna dla wykonywania wielu zadań w życiu.Dyscyplina informatyki dotyczy wielu rodzajów problemów, w tym znalezienie skutecznych sposobów wyszukiwania informacji, aby uzyskać przydatne wyniki.Wyszukiwanie binarne to tylko jeden z wielu dostępnych algorytmów do wyszukiwania danych.