Ocena brak

Opisz schemat działania algorytmu wyszukiwania binarnego z listy uporządkowanej. Jaką ten algorytm ma złożoność?

Autor /Barnim7777 Dodano /29.12.2011

Działanie algorytmu wyszukiwania binarnego z listy uporządkowanej rozpoczyna się od porównania ze wzorcem poszukiwanego elementu, elementu znajdującego się w samym środku listy. Jeżeli nie trafiono w poszukiwany element wiadomo już, w której połowie listy mamy go szukać (bo lista jest uporządkowana). Wtedy rozpoczynamy badanie odpowiedniej połowy listy od porównania wzorca elementu poszukiwanego z jej elementem środkowym. Jeśli znów nie trafiliśmy powtarzamy działania dalej. W pewnym momencie algorytm zawsze trafi na poszukiwany element, chyba że nie ma go na liście.

Złożoność czasowa tego algorytmu wynosi F(N)=O(logN), gdzie N jest zależne od ilości elementów.

Długość listy:

- 20 elementów (5 porównań)

- 1000000 elementów (20 porównań)

Podobne prace

Do góry