Wstęp

Pewnie grałeś już w grę "zgadnij liczbę", polega ona na tym, że jeden gracz prubuje zgadnąć, jaką liczbę, z określonego zakresu (np. 1-100), wymyślił drugi gracz. W tym celu może strzelać, wskazując w jakąś liczbę i otrzymując w odpowiedzi informację, czy szukana liczba jest miejsza, większa, czy równa wskazanej przez niego liczbie.

Zobaczmy przykładowe rozgrywki:

Zobaczmy te same rozgrywki, ale w optymalniejszej formie:

Ten sposób nazywa się binsearch.

Działanie

Bierzemy punkt po środku zakresu, by zmiejszyć zakres o połowę.

Dzięki temu dojdziemy do rozwiązania w ok. log n ruchów, gdzie n to długość początkowego zakresu. Oznacza to, że złożoność obliczeniowa tego rozwiązania to O(log n).

Do czego jest potrzebny ten algorytm?

Jednak jak to wykorzystać? Przecież w zadaniach raczej wczytujemy jakąś liczbę, a nie próbujemy ją zgadnąć!

Binsearch przydaje się, gdy chcemy znaleźć szybko pierwsze wystąpienie danej liczby w posortowanej tablicy (w przypadku gry "zgadnij liczbę" w zbiorze liczb naturalnych od 1 do 100), a dokładniej znaleźć jej indeks (jeśli ta liczba w ogóle istnieje w tej tablicy).

Popatrzmy na ten przykład:

Mamy tablicę tab = [1, 3, 8, 10, 12, 13, 15, 17]

Jak znajdziesz w niej pozycję liczby 15?

Możliwe, że przeszedłbyś po elementach, aż doszedłbyś do 15, ale lepiej zrobić to tak:

1. Bierzemy środkowy element tablicy - 10 (indeks 3 - pierwszy element ma indeks 0).
2. 10 < 15, więc odcinamy 10 i wszystkie liczby przed nią (jeszcze mniejsze). Teraz nasza tablica wygląda tak: tab = [12, 13, 15, 17]
3. Znowu bierzemy środkowy element "nowej" tablicy - 13 (indeks 5) (co prawda nie jest on idealnie środkowy, ale środkowy element nie istnieje).
4. 13 < 15, więc odcinamy 13 i wszystkie liczby przed nią (jeszcze mniejsze). Teraz nasza tablica wygląda tak: tab = [15, 17]
5. Znowu bierzemy środkowy element "nowej" tablicy - 15 (indeks 6).
6. 15 = 15, więc odcinamy wszystkie elementy za nią (nie zawsze kończymy w tym przypadku programu, bo możliwe jest, że przed tą 15 jest jeszcze inna 15). Teraz nasza tablica wygląda tak: tab = [15]
7. Mamy jeden element, więc jest to ten właściwy (indeks 6).

Ale skąd znamy te indeksy?

Tak naprawdę w programie nie będziemy usuwać elementów tylko zmieniać zakres, który rozpatrujemy.

Czy to się opłaca?

Wczytywanie jest liniowe, więc nasz program nie będzie miał złożoności O(log n), tylko O(n), dlatego binsearch opłaca się tylko wtedy, gdy mamy znaleźć wiele elementów we wczytanej tablicy.

Coraz bliżej kodu

Zapiszmy nasz teraźniejszy przedział indeksów jako [p, k] (p - początek, k - koniec). Początkowo p = 0, a k = długość tablicy - 1.

Za każdym razem znajdujemy indeks elementu środkowego S = ⌊p + (k - p)/2⌋ = ⌊(2p + k - p)/2⌋ = ⌊(p + k)/2⌋.

Oznaczmy wartość, której indeks mamy znaleźć jako a.

• Jeśli tab[S] < a to zmieniamy p na S+1 (odcinamy tab[S] i wszystkie liczby przed nią).
• Jeśli tab[S] = a to zmieniamy k na S (szukamy pierwszego wystąpienia liczby a, a nie mamy pewności, że jest to tab[S]; za to na pewno nie wchodzą w grę dalsze liczby).
• Jeśli tab[S] > a to zmieniamy k na S-1 (odcinamy tab[S] i wszystkie liczby za nią).
• Kończymy wtedy, kiedy p = k, czyli mamy w zakresie tylko jeden element, a wynikiem jest p lub b.

Przykład:

tab = [1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 16, 16, 17], a = 16

iteracja	p	k	S	tab[S]
0	0	12	6	9
1	7	12	9	12
2	10	12	11	16
3	10	11	10	16
4	10	10	-	-

Pierwsze wystąpienie liczby 16 w tej tablicy jest na indeksie 10.

Nie ma szukanej liczby - co wtedy?

Co jednak, gdy w tablicy nie ma szukanej liczby?

tab = [1, 2, 4, 8, 16, 32], a = 7

iteracja	p	k	S	tab[S]
0	0	5	2	4
1	3	5	4	16
2	3	3	-	-

Przecież tab[3] = 8, a nie 7. Co więc oznacza te 3?

Zmodyfikujmy definicję:

tab[ans] jest najmniejszą liczbą ≥ a. Gdy a istnieje w tablicy, to ans to indeks jej pierwszego wystąpienia.

Implementacja w Pythonie:

1. Rekurencja:

2. Iteracja:

Implementacja w C++:

1. Rekurencja:

2. Iteracja:

Binsearch w drugą stronę

Binsearch w drugą stronę znajduje indeks największej liczby z posortowanej tablicy, która jest ≤ a. Jeśli ta liczba jest równa a, to znajduje jej ostatnie wystąpienie.

Jest on częściej stosowany niż "zwykły" binsearch.

Różnice:

Jedyne różnice są w warunkach i warunku zakączenia algorytmu:

Zapiszmy nasz teraźniejszy przedział indeksów jako [p, k] (p - początek, k - koniec). Początkowo p = 0, a k = długość tablicy - 1.

Za każdym razem znajdujemy indeks elementu środkowego S = ⌊p + (k - p)/2⌋ = ⌊(2p + k - p)/2⌋ = ⌊(p + k)/2⌋.

Oznaczmy wartość, której indeks mamy znaleźć jako a.

• Jeśli tab[S] < a to zmieniamy p na S (odcinamy wszystkie liczby przed tab[S] - jeśli nie ma większych liczb ≤ a, to to jest rozwiązanie, dlatego nie można uciąć tab[S]).
• Jeśli tab[S] = a to zmieniamy p na S (szukamy ostatniego wystąpienia liczby a, a nie mamy pewności, że jest to tab[S]; za to na pewno nie wchodzą w grę poprzednie liczby).
• Jeśli tab[S] > a to zmieniamy k na S-1 (odcinamy tab[S] i wszystkie liczby za nią).
• Kończymy wtedy, kiedy k-p ≤ 1 (bo jak k-p = 1, czyli S = p oraz jak tab[S]≤a, to program się zapętla), a wynikiem jest k.

Zauważmy, że dla tab[S] < a i tab[S] = a robimy to samo (ustawiamy p na S), więc możemy zamienić te dwa warunki w jeden:

Jeśli tab[S] ≤ a, to zmieniamy p na S.

Implementacja binsearcha "w drugą stronę" w Pythonie

Rekurencja:

Iteracja:

Implementacja binsearcha "w drugą stronę" w C++

Rekurencja:

Iteracja:

Co, jak nie mamy posortowanej tablicy?

Przy dużej ilości zapytań opłaca się nawet posortować tablice, żeby zrobić wiele razy binsearcha, niż wyszukiwać elementy liniowo!

Przewaga czasowa

ilość elementów w tablicy	binsearch - O(log n)	liniowe wyszukiwanie elementów - O(n)
103	10 operacji - 0 s	103 operacji - 0 s
106	20 operacji - 0 s	106 operacji - 0 s
109	30 operacji - 0 s	109 operacji - 1 s
1012	40 operacji - 0 s	1012 operacji - 1000 s = 16 min
10100	340 operacji - 0 s	10100 operacji - 10100 s = 1070 lat!

Gotowe funkcje do C++

W C++ są już gotowe funkcje do binsearcha:

• lower_bound()

  - znajduje największy element ≤ a w posortowanej tablicy.

• upper_bound()

  - znajduje najmniejszy element > a w posortowanej tablicy.

• binary_search()

  - mówi, czy w posortowanej tablicy występuje dany element.