69106

Wyszukiwanie binarne oszacowanie złożoności

powy zszy algorytm to binarne wyszukiwanie elementu X w NDelementowej tablicy T

idea algorytmu polega na skracaniu obszaru poszukiwa ń o połow, e liczba porównań' wykonywanych w algorytmie to liczba, określająca, ile razy wielko YcN mo znapodzieli c przez 2, zanim zostanie ona zredukowana do 1 czyli log2N zło zono s'c algorytmu wynosi zatem O(logN)

podejś cie algorytmu do problemu polegają, ce na sukcesywnym skracaniu zadania nosi nazw, e metody dziel i zwyci, e zaj