Wyszukiwanie Binarne

Jak w posortowanym zbiorze znaleźć konkretną wartość? Najprościej przeliterować się po każdym elemencie. Czyli jeśli wybierzesz liczbę z przedziału 1-100 i za każdym razem informacją zwrotną będzie czy dana liczba jest większa czy mniejsza od podanej przeze mnie, to w najgorszym wypadku będę potrzebował aż 100 prób żeby odkryć o jaką liczbę Ci chodzi.

A jak to zrobić szybciej? Tutaj przychodzi z pomocą algorytm wyszukiwania binarnego, tzn zgadujemy zawsze wartością równą połowy danego zbioru, czyli:

  1. Mając zakres wartości od 1 do 100, zaczynam od środka czyli 50.
  2. Otrzymując od Ciebie informację czy Twoja liczba jest mniejsza czy większa eliminuje 50 rekordów.
  3. Zakładając, że wybrana liczba to 33, moją następną odpowiedzią będzie 25, a następny zbiór będzie się zawierał w przedziale 25 -50 itd.
  4. Czyli maksymalna liczba prób przy zbiorze 100-elementowym wyniesie 7.

Dla porównania przy zbiorze 1 000 000 000 wyszukiwanie proste potrzebuje maksymalnie 1 000 000 000 a wyszukiwanie binarne tylko 32 próby.

Implementacja wyszukiwania binarnego wygląda następująco:

public int binarySearch (TreeSet<Integer> listOfNumber, int searchNumber)
{
int min = listOfNumber.first();
int max = listOfNumber.last();
int quess;

while (min <= max)
{
quess = (( min + max ) / 2) + 1;

if (quess == searchNumber)
{
return quess;
}
if (quess < searchNumber)
{
min = quess;
}
if (quess > searchNumber)
{
max = searchNumber;
}
}

return Integer.parseInt(null);
}

Używam TreeSeta gdyż z automatu jest posortowany. Nie ładnie ale rzucam nullem gdy wybrana liczba nie zawiera się w zbiorze.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *