Wyszukiwanie binarne.pdf

Wyszukiwanie binarne.

Autor: Adam Polak

Wstęp

Wyszukiwanie binarne jest techniką prostą i intuicyjną, lecz często bardzo trudno dostrzec,

że postawiony przed nami problem można łatwo rozwiązać z jej użyciem. Celem tego artykułu jest

wprowadzenie czytelnika w szczegóły implementacji wyszukiwania binarnego i zaprezentowanie

szeregu różnorodnych problemów, których rozwiązania się na nim opierają.

Symbol lg oznacza w domyśle logarytm dwójkowy, a wszystkie kody pisane są w języku

Prosta gra

Andrzej i Bartek grają w następującą grę: Bartek wybiera dowolną liczbę naturalną mniejszą

od pewnego ustalonego n, a Andrzej próbuje odgadnąć, co to za liczba. Za każdym razem Bartek

mówi koledze, czy trafił, czy nie. Nietrudno zauważyć, że w pesymistycznym przypadku Andrzej

będzie zmuszony zapytać n razy, zanim uzyska odpowiedź.

Wprowadźmy pewne ułatwienie. Niech Bartek za każdym razem mówi, czy podana przez

Andrzeja liczba jest mniejsza, czy większa od szukanej. Teraz optymalna strategia dla zgadującego

jest następująca: pyta się o liczbę w połowie zakresu (czyli [n/2]), jeśli liczba Bartka jest większa,

zawęża zakres poszukiwań do (n/2; n), jeśli mniejsza do (0; n/2), po czym kontynuuje, pytając się o

środkową wartość z nowego zakresu.

Zauważmy, że za każdym razem Andrzej zmniejsza swój zakres poszukiwań o połowę, tak

więc po najdalej lg(n) (lg – logarytm dwójkowy) krokach zawęzi ów zakres do jednej liczby.

Pozornie niewielka zmiana zasad gry pozwala na znaczące skrócenie czasu potrzebnego na

wygranie. Strategia przyjęta przez Andrzeja zwana jest wyszukiwaniem binarnym.

Wyszukiwanie binarne w problemach algorytmicznych

Zastanówmy się, jakie cechy musi mieć problem, by było możliwe rozwiązanie go przy

użyciu wyszukiwania binarnego. Po pierwsze zbiór możliwych rozwiązań musi być skończony (a

tym samym ograniczony). Zauważmy, że gdy poszukujemy rozwiązania w pewnym przedziale

liczb rzeczywistych, zbiór rozwiązań jest ograniczony, ale teoretycznie nieskończony – jednakże

interesuje nas rozwiązanie z pewną dokładnością, zatem de facto zbiór ów ma skończoną liczbę

elementów. Po drugie zweryfikowanie poprawności danego rozwiązania musi dawać nam

informację na temat położenia rozwiązania poprawnego.

Rozważmy prosty problem: mamy daną, posortowaną w porządku niemalejącym tablicę

liczb całkowitych tab[n], pytamy się pod jakim indeksem w tej tablicy znajduję się wartość x

(zakładamy, że na pewno gdzieś taka wartość wystąpi). Zbiór możliwych rozwiązań jest skończony

i ograniczony (jest to liczba naturalna z zakresu <1; n>), a odczytanie wartości z danej komórki

tabeli, mówi nam czy poszukiwany indeks jest większy, czy mniejszy od aktualnie sprawdzanego

(ponieważ tablica jest posortowana). Zatem zadanie to da się rozwiązać z użyciem wyszukiwania

binarnego. Szkic takiego rozwiązania przedstawia poniższy kod:

// tab[] - tablica liczba, n - rozmiar tablicy

int find( int a) // a - szukana wartość

{

int l = 0;

int r = n;

while ((r-l)>1)

{

C++.

int s = (r+l)/2;

if (tab[s]==a) return s;

if (tab[s]<a) l=s; else r=s;

}

if (tab[l]==a) return l; else return r;

}

Inne przykłady zastosowania wyszukiwania binarnego

Zastanówmy się nad następującym zadaniem: wyznaczyć rozwiązania równania

x 2 =cos(x*Π) w zakresie <0;1>. Zauważmy, że w danym zakresie funkcja x 2 jest ściśle rosnąca, zaś

cos(x*Π) ściśle malejąca – przecinają się więc najwyżej w jednym miejscu. Dla x=0 mamy x 2 =0 i

cos(x*Π)=1, zaś dla x=1: x 2 =1 i cos(x*Π)=-1. Obie funkcje są ciągłe, zatem na mocy twierdzenia

Darboux podane równanie ma dokładnie jedno rozwiązanie w podanym zakresie. Widzimy więc, że

rozwiązanie z dowolną dokładnością (uzyskanie wyników dokładnych w liczbach rzeczywistych

jest oczywiście niemożliwe dla komputera) możemy obliczyć z pomocą wyszukiwania binarnego.

Będziemy zawężać zakres poszukiwań, dopóki nie będzie on dostatecznie mały (czyli do

osiągnięcia zadanej dokładności). Jeśli w badanym przez nas punkcie lewa strona równania będzie

mniejsza od prawej, przechodzić będziemy do prawej połówki przedziału, w przeciwnym

przypadku do lewej. Rozwiązanie to ilustruje poniższy kod:

#include <cstdio>

#include <cmath>

using namespace std;

const double D=0.00001;

int main()

{

double l,r,s;

l=0; r=1;

while ((r-l)>D)

{

s = (l+r)/2;

if ((s*s)<cos(s* M_PI )) l=s; else r=s;

}

printf("%lf\n",s);

return 0;

}

Pora na zadanie, w którym rozwiązanie wyszukiwaniem binarnym nie narzuca się od razu.

Dysponujemy stajnią, w której znajduje się n boksów, ustawionych w linii prostej. Boks i-ty od

początku stajni oddalony jest o całkowitą ilość jednostek - x i . Naszym zadaniem jest ulokowanie w

stajni k koni. Niestety konie nie przepadają za sobą i zależy nam na takim ich rozmieszczeniu, by

konie stały możliwe najdalej od siebie. Konkretniej, maksymalizujemy odległość między stojącymi

najbliżej siebie końmi. Poszukiwaną wartością jest właśnie ta odległość. Nietrudno wymyślić

rozwiązania opierające się w mniejszym lub większym stopniu na strategii brute-force.

Skoncentrujmy się jednak na rozwiązaniu optymalnym o asymptotycznej złożoności czasowej

O(nlg(x n )). Zauważmy, że poszukiwana wartość jest na pewno większa od zera i mniejsza od

łącznej długości stajni (czyli x n ). Mamy już więc dany zakres poszukiwań. Pozostaje sprawdzenie,

jak się ma dana odległość d do rozwiązania optymalnego. Będziemy robić to w następujący sposób:

wstawiamy konia do pierwszego boksu. Przeglądamy kolejne boksy i gdy napotkamy pierwszy,

odległy od ostatnio obsadzonego o d lub więcej, wstawiamy do niego kolejnego konia. Postępujemy

tak, dopóki nie dojdziemy do końca stajni. Jeśli udało nam się wstawić w ten sposób k lub więcej

koni, wiemy, że d jest mniejsze lub równe rozwiązaniu optymalnemu. Jeśli lokując konie w podany

sposób, znaleźliśmy miejsce dla mniej niż k zwierząt, to sprawdzana przez nas wartość d jest zbyt

duża. Weryfikacji danej wartości d możemy dokonać w czasie O(n) – przeglądamy kolejno n

boksów i w czasie stałym rozstrzygamy, czy możemy umieścić w danym boksie konia. Po

sprawdzeniu najwyżej lg(x n ) odległości, znajdziemy optymalne rozwiązanie. Zadanie to okazuje się

bardzo proste, zarówno koncepcyjnie, jak i implementacyjnie, jednakże osobie nieobeznanej z

wyszukiwaniem binarnym kłopot może sprawić dostrzeżenie przedstawionego rozwiązania. Pełne

rozwiązanie przytoczonego zadania znajduje się poniżej.

#include <cstdio>

const int MAX = 100000;

int n,k,temp;

int x[MAX];

bool czy_za_duzo( int a)

{

int temp=0;

int last = 0;

for ( int i=0; i<n; i++)

if ((x[i] - x[last])>=a) {last = i; temp++;}

if (temp<k) return 1;

return 0;

}

int main()

{

scanf("%d%d",&n,&k);

k--;

for ( int i=0; i<n; i++) {scanf("%d",&x[i]);}

int l = 0;

int r = x[n-1];

while ((r-l)>1)

{

temp = (l+r)/2;

if (czy_za_duzo(temp)) r=temp; else l=temp;

}

if (!czy_za_duzo(r)) temp = r; else temp = l;

printf("%d\n",temp);

return 0;

}

Podsumowanie

Wyszukiwanie binarne jest algorytmem prostym implementacyjnie i dość intuicyjnym.

Często pozwala w niezwykle elegancki i krótki sposób rozwiązać problem w czasie optymalnym

lub niewiele różniącym się od optymalnego (np. liniowologarytmicznie zamiast liniowo).

Zazwyczaj największy kłopot sprawia uświadomienie sobie, że dane zadanie można rozwiązać z

użyciem tej techniki lub innego algorytmu, opierającego się na podobnym pomyśle. Dlatego, gdy

przez długi czas nie możemy znaleźć rozwiązania pewnego problemu, radzę przemyśleć, czy tym

razem wyszukiwanie binarne nie przyjdzie nam z pomocą. Czytelnikom, chcącym sprawdzić swoje

umiejętności w posługiwaniu się opisaną metodą, proponuje rozwiązanie następujących zadań:

● Przeprowadzka z Zawodów Stałych OPSS

● Najazd z II etapu XIII Olimpiady Informatycznej.

● Odważniki z III etapu XIV Olimpiady Informatycznej

Dodatek: Schemat algorytmu wyszukiwania binarnego

START

min = 0

max = n

Tak

(min+max)/2

to poprawne

rozwiązanie

Nie

wypisz

(min+max)/2

Tak

rozwiązanie

jest większe

Nie

min = (min+max)/2

max = (min+max)/2

STOP

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: