Oto wikipedia wpis w
Jeśli spojrzysz na proste podejście iteracyjne. Po prostu eliminujesz połowę elementów do wyszukania, aż znajdziesz element, którego potrzebujesz.
Oto wyjaśnienie, w jaki sposób tworzymy wzór.
Powiedzmy, że początkowo masz N elementów, a następnie przy pierwszej próbie zrobisz „N / 2”. Gdzie N jest sumą dolnej granicy i górnej granicy. Pierwsza wartość czasu N byłaby równa (L + H), gdzie L to pierwszy indeks (0), a H to ostatni indeks listy, której szukasz. Jeśli masz szczęście, element, który próbujesz znaleźć, będzie w środku [np. Szukasz 18 na liście {16, 17, 18, 19, 20}, a następnie obliczasz ⌊ (0 + 4) / 2⌋ = 2, gdzie 0 to dolna granica (L - indeks pierwszego elementu tablicy) a 4 to wyższa granica (H - indeks ostatniego elementu tablicy). W powyższym przypadku L = 0 i H = 4. Teraz 2 to indeks znalezionego elementu 18. Bingo! Znalazłeś to.
Gdyby przypadek był inną tablicą {15,16,17,18,19}, ale nadal szukałeś 18, nie miałbyś szczęścia i zrobiłbyś pierwsze N / 2 (czyli ⌊ (0 + 4) / 2⌋ = 2, a następnie zdaj sobie sprawę, że element 17 pod indeksem 2. nie jest liczbą, której szukasz. Teraz wiesz, że nie musisz szukać co najmniej połowy tablicy podczas następnej próby iteracyjnego wyszukiwania. wysiłek związany z wyszukiwaniem jest zmniejszony o połowę, więc zasadniczo nie przeszukujesz połowy listy elementów, które przeszukiwałeś wcześniej, za każdym razem, gdy próbujesz znaleźć element, którego nie mogłeś znaleźć w poprzedniej próbie.
Więc najgorszy byłby przypadek
[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
tj .:
N / 2 1 + N / 2 2 + N / 2 3 + ..... + N / 2 x … ..
aż… zakończysz wyszukiwanie, gdzie w szukanym elemencie znajduje się na końcu listy.
To pokazuje, że w najgorszym przypadku osiągniesz N / 2 x, gdzie x jest takie, że 2 x = N
W innych przypadkach N / 2 x gdzie x jest takie, że 2 x <N Minimalna wartość x może wynosić 1, co jest najlepszym przypadkiem.
Ponieważ matematycznie najgorszym przypadkiem jest sytuacja, w której wartość
2 x = N
=> log 2 (2 x ) = log 2 (N)
=> x * log 2 (2) = log 2 (N)
=> x * 1 = log 2 (N)
=> Bardziej formalnie ⌊log 2 (N) + 1⌋