Binary Search

Do czego służy?

Algorytm wyszukiwania binarnego(Binary Search) służy do szybkiego wyszukiwania w danym POSORTOWANYM ciągu liczb jakiejś liczby. Możemy szukać pierwszego wystąpienia, drugiego wystąpienia, pierwszej większej lub pierwszej niemniejszej liczby.

Algorytm

Zamiast przeszukiwać cały ciąg, skorzystajmy z tego, że jest posortowany. Będziemy sprawdzać środkowy element w ciągu. (Tutaj omówię przypadek jeśli znajdujemy pierwsze wystąpienie w ciągu posortowanym niemalejąco) Jeśli element jest większy lub równy od szukanego odrzucamy wszystkie liczby po prawej. W przeciwnym wypadku wszystkie liczby po lewej. Jak już zostanie nam tylko jedna liczba, to jest ta liczba, którą szukamy.

Przykład

Dla przykładowego ciągu: 1 2 2 2 3 4 4 znajdźmy pierwsze wystąpienie 2.
1 2 3 4 5 6 7 (indeksy)
1 2 2 2 3 4 4 (wartości)
1. Bierzemy indeks 4. Jest tam wartość 2, więc odrzucamy wszystko od indeksu 5.
2. Bierzemy indeks 2, gdzie też mamy dwójkę, więc odrzucamy wszystko od indeksu 3.
3. Bierzemy indeks 1. Tam mamy 1, czyli to nie jest nasza szukana wartość. Odrzucamy więc wszystko do indeksu 1 (włącznie).
4. Zauważmy, że teraz został nam jeden element do rozpatrzenia, na indeksie 2. Jest to więc nasz szukany element!

implementacja i złożoność

implementacja w c++:

const int MAXI = 5e5 + 7;
int tablica[MAXI];

int BinarySearch(int pocz, int kon, int co){
int sro;
while(pocz < kon){
sro = (pocz + kon + 1) / 2;
if(tablica[sro] < co){
pocz = sro + 1;
}
else{
kon = sro;
}
}
return pocz;
}

implementacja w python:

maxi = 1000007
lista = [0 for i in range(maxi)]

def BinarySearch(kon, war):
pocz = 1
while (pocz < kon):
sro = (pocz + kon) // 2
if(lista[sro - 1] < war):
pocz = sro + 1
else:
kon = sro
return pocz

złożoność:

O(log₂(n))

Zadania

Binary Search po wyniku

Do czego służy?

Algorytm Binary Search po wyniku służy to wyszukiwania po wartościach funkcji result, która daje nam wyniki dla danej wartości. Te wyniki muszą być niemalejące/nierosnące. Chcemy wyszukać daną wartość wyniku, a zwrócić wartość, która daje ten wynik.

Algorytm

Binary Search po wyniku polega na prawie tym samym co zwykły Binary Search, tylko wyszukujemy po wartości, od której zależy wynik. Wynik musi spełniać warunki, że:
do pewnego momentu wynik spełnia jakąś własność a potem nie spełnia lub na odwrót
wyniki są niemalejące lub nierosnące
Gdzie jako wynik mamy funkcję result, w której na podstawie treści zadania wykonujemy operacje dające nam wynik (dla danej wartości).

Przykład

Przykładu nie ma, ponieważ omawiałam ogólnie ten algorytm, bez uściślenia funkcji result. W takim wypadku nie da się zasymulować przykładu.

implementacja i złożoność

implementacja w c++:

int BinarySearchResult(int pocz, int kon){
int sro;
while(pocz < kon){
sro = (pocz + kon + 1) / 2;
if(Result(sro) == true){
pocz = sro;
}
else{
kon = sro - 1;
}
}
return pocz;
}

implementacja w python:

def BinarySearchResult(pocz, kon):
while(pocz < kon):
sro = (pocz + kon + 1) / 2
if(Result(sro) == True):
pocz = sro
else:
kon = sro - 1
return pocz

złożoność:

O(log₂(n))