Spisu treści:
Definicja - Co oznacza wyszukiwanie binarne?
Algorytm wyszukiwania binarnego służy do znalezienia pozycji określonej wartości zawartej w posortowanej tablicy. Algorytm wyszukiwania, działający zgodnie z zasadą dzielenia i zdobywania, może być dość szybki, ale zastrzeżeniem jest to, że dane muszą być posortowane. Działa, rozpoczynając wyszukiwanie w środku tablicy i pracując od pierwszej dolnej lub górnej połowy sekwencji. Jeśli wartość mediany jest niższa niż wartość docelowa, oznacza to, że wyszukiwanie musi iść wyżej, jeśli nie, to musi spojrzeć na malejącą część tablicy.
Wyszukiwanie binarne jest również znane jako wyszukiwanie z połówkami lub wyszukiwanie logarytmiczne.
Techopedia wyjaśnia wyszukiwanie binarne
Wyszukiwanie binarne to szybka i skuteczna metoda znajdowania określonej wartości docelowej z zestawu zamówionych elementów. Zaczynając na środku posortowanej listy, może skutecznie zmniejszyć obszar wyszukiwania o połowę, określając, czy należy wznieść się czy zejść z listy na podstawie wartości mediany w porównaniu z wartością docelową.
Na przykład z wartością docelową 8 i przestrzenią wyszukiwania od 1 do 11:
- Znaleziono medianę / wartość średnią i ustawiono tam wskaźnik, który w tym przypadku wynosi 6.
- Cel 8 jest porównywany z 6. Ponieważ 6 jest mniejsze niż 8, cel musi znajdować się w wyższej połowie.
- Wskaźnik jest przenoszony do następnej wartości (7) i porównywany z celem. Jest mniejszy, dlatego wskaźnik przesuwa się do następnej wyższej wartości.
- Wskaźnik jest teraz na 8. Porównując to do celu, jest to dokładne dopasowanie, dlatego cel został znaleziony.
Korzystając z wyszukiwania binarnego, cel musiał zostać porównany tylko z trzema wartościami. W porównaniu do wyszukiwania liniowego zaczynałby się od pierwszej wartości i przesuwał w górę, wymagając porównania celu z ośmioma wartościami. Wyszukiwanie binarne jest możliwe tylko z uporządkowanym zestawem danych; jeśli dane są losowo uporządkowane, wówczas wyszukiwanie liniowe przyniosłoby wyniki przez cały czas, podczas gdy wyszukiwanie binarne prawdopodobnie utknęłoby w nieskończonej pętli.
