Wyszukiwanie binarne w Javie

Poszukiwanie tablicy położenia wartości i sortowanie tablicy to dwa różne procesy. Wyszukiwanie oznacza sprawdzenie, czy wartość nazywana kluczem znajduje się w tablicy. Sortowanie oznacza umieszczanie wszystkich wartości w tablicy w określonej kolejności (rosnący lub zstępujący). Jeśli tablica nie jest sortowana, a wyszukiwanie jest wymagane, program musi zacząć od indeksu zero, a następnie do indeksu 1, a następnie indeks 2 i tak dalej, dopóki nie osiągnie indeksu wartości, której szuka. Jeśli wartość występuje więcej niż raz, należy zwrócić pierwszy indeks.

Jeśli tablica jest najpierw sortowana, powiedzmy w kolejności rosnącej, wówczas wyszukiwanie staje się łatwe. Indeks jest mniejszy niż indeks elementu środkowego, jeśli klucz jest mniejszy niż wartość wskaźnika środkowego lub indeks jest równy lub większy niż wartość wskaźnika środkowego, jeśli wartość jest równa lub większa niż większa niż większa niż większa wartość średniej indeksu.

Więc po prostu podziel tablicę na dwa. Jeśli wartość leży po lewej stronie, nie trzeba marnować czasu na przeszukiwanie prawej strony; Po prostu przeszukaj lewą stronę. Jeśli wartość leży po prawej stronie, nie trzeba marnować czasu na przeszukiwanie lewej strony; Po prostu przeszukaj prawą stronę. Ponieważ tablica jest już całkowicie posortowana, kiedy doszło do każdej strony, jest ponownie podzielona na dwa i przeszukana jest tylko jedna z nowych par bok. W rzeczywistości wyszukiwanie w ten sposób jest po prostu podzielone na dwa, dopóki indeks wartości nie zostanie osiągnięty. Żadne rzeczywiste wyszukiwanie pod względem skanowania, ponieważ tablica jest już sortowana. Może być trochę niewielkiego poruszania się w prawo, a podczas poszukiwań niewielki poruszający się w lewo.

Binarny implikuje, dwa. I tak ten rodzaj wyszukiwania nazywa się wyszukiwaniem binarnym. Istnieją różne zamówienia sortowania: wszystkie wartości w tablicy można całkowicie sortować w kolejności rosnącej lub zejść. Tablicę można również posortować w formacie drzewa binarnego wyszukiwania. To nie jest całkowite sortowanie w kolejności rosnącej lub malejącej. Jednak wyszukiwanie algorytmu binarnego nadal działa z tym formatem.

W tym artykule wyjaśniono wyszukiwanie binarne Java. Algorytm wyszukiwania binarnego w Java pracuje na tablicy, która jest już posortowana. W tym artykule rozważane jest tylko całkowite sortowanie w kolejności rosnącej. Ten artykuł rozpoczyna się od ilustracji algorytmu wyszukiwania binarnego. Następnie wyjaśnia, jak używać metod BinarySearch () klasy Java tablic.

Treść artykułu

• Ilustracja algorytmu wyszukiwania binarnego
• Pakiet Java i klasa do wyszukiwania binarnego
• Konstruowanie tablicy do wyszukiwania
• Metody wyszukiwania binarnych klas tablicowych
• Wyszukiwanie zasięgu
• Wniosek

Ilustracja algorytmu wyszukiwania binarnego

Rozważ następującą sekwencję znaków:

P V D Q S X T H N O

Umieszczając się w kolejności rosnącej, sekwencja staje się:

D h n o p q s t v x

Jest tutaj dziesięć elementów. Liczenie indeksu zaczyna się od 0. Gdy liczba elementów jest równa (e.G., 10), wskaźnik elementu środkowego jest uważany za liczbę elementów podzielonych przez dwa. W takim przypadku 10/2 to 5. Gdy liczba elementów jest dziwna, wskaźnik środkowego elementu jest traktowany jako część całkowitą (liczba całkowita) liczby elementów podzielonych przez dwa.

Istnieją dwie listy powyżej. Drugi to sortowana forma pierwszego. Załóżmy, że wyszukiwanie miała wiedzieć, czy S był obecny na pierwszej liście. Lista musiałaby najpierw posortować, aby mieć drugą listę w schemacie wyszukiwania binarnego. Na posortowanej liście indeks dla pozycji środkowej wynosi 5 = 10/2. To odpowiada wartości, Q. Wyszukiwanie zatrzymuje się, aby sprawdzić, czy Q to S, wartość szukała. Jeśli tak, to wyszukiwanie zatrzymuje się. Jeśli tak nie.

W tym przypadku leży w zakresie od Q w górę, który następnie jest wybierany. Nie marnuje się czasu na przeszukiwanie dolnej połowy listy (tablica). Tak więc ten nowy zakres musi być podzielony na dwa. Ten zakres składa się z 5 elementów. 5 /2 = 2 i 1/2. Środkowy element znajduje się w pozycji 2 tego nowego zakresu. Odpowiada to t, jeśli liczenie z zera ma zacząć od q. Rzeczywisty wskaźnik t wynosi 7.

Dolny lub lewy zakres składa się teraz z (Q S), podczas gdy nowy górny lub prawy zasięg składa się teraz z (T V X). Jest nowym środkowym elementem, t takim samym jak s, wartość szukała? - NIE. W którym zasięgu leży; Czy jest w dolnym zakresie, (Q S) lub w górnym zakresie (T V x)? - Leży w niższym zakresie.

Tak więc niższy zakres (Q S) należy następnie podzielić na dwa. Po zakończeniu, środkowy indeks tego zakresu odpowiada S (2/2 = 1, ponieważ Q jest w nowym indeksie 0). Rzeczywisty indeks dla S wynosi 6 (D znajduje się na oryginalnym indeksie 0). Wskaźnik znalezionej wartości powinien zostać zwrócony.

Klucz nie odnaleziony

Wartość poszukująca nazywa się kluczem. Sortowana lista ma dwa indeksowanie, jak pokazano poniżej:

D	H	N	O	P	Q	S	T	V	X
0	1	2	3	4	5	6	7	8	9
-1	-2	-3	-4	-5	-6	-7	-8	-9	-10

Pierwszy rząd tej tabeli ma posortowaną listę. Drugi rząd ma normalne indeksowanie. Trzeci rząd ma rodzaj ujemnego indeksowania, w którym pierwszy element znajduje się na indeksie -1, drugi jest w indeksie -2, trzeci przy indeksie -3 i tak dalej.

Jeśli klucz zostanie znaleziony, algorytm Java zwróci normalny wskaźnik, począwszy od 0. Jeśli klucz nie zostanie znaleziony, algorytm Java zwróci negatywny wskaźnik dla pozycji, który byłby zajęty (zakładając, że tablica rozszerzona na prawą o jeden element).

Pakiet Java i klasa do wyszukiwania binarnego

Schemat wyszukiwania binarnego Java działa w tablicy, która jest już posortowana. Tablice klas Java, które są w Javie.Util.* Pakiet, ma metody binarne () do binarnego wyszukiwania tablicy, która jest już posortowana. Każda z tych metod zwraca liczbę całkowitą, która jest normalnym indeksem, jeśli klawisz zostanie znaleziony lub indeks ujemny, jak wyjaśniono powyżej, jeśli nie znaleziono klucza. Dwie z tych metod dotyczy znaków.

Konstruowanie tablicy do wyszukiwania

Druga lista powyżej zostanie użyta do zilustrowania kodowania wyszukiwania binarnego w Javie. Do konstruowania posortowanej tablicy można użyć następującego stwierdzenia:

char [] arr = nowy char [] 'd', „h”, „n”, „o”, „p”, „q”, „s”, „t”, „v”, „x” ;

Schemat wyszukiwania binarnego Java działa na liście, która jest już posortowana.

Metody wyszukiwania binarnych klas tablicowych

W tym rozdziale zostanie użyta powyższa gama znaków. Metody wyszukiwania binarnego znajdują się w klasie tablic Java.Util.* pakiet. Ten pakiet musi zostać zaimportowany, aby użyć klasy tablic.

Wszystkie metody klasy tablic są metodami statycznymi. Oznacza to, że obiekt nie musi być utworzony utworzeniem żadnej z jego metod, które należy zastosować. Dwie z tych metod to binarne metody wyszukiwania dla znaków. Składnia jednej z binarnych metod wyszukiwania, dla znaków:

public static int binarySearch (char [] a, char key)

Znaleziono następujące programy S, które zostaną znalezione:

Importuj Java.Util.*;
Klasa publiczna THEClass
public static void main (string [] args)
char [] arr = nowy char [] 'd', „h”, „n”, „o”, „p”, „q”, „s”, „t”, „v”, „x” ;
int ret = tablice.BinarySearch (arr, „s”);
System.na zewnątrz.println (ret);

Wyjście to 6. Poniższy segment kodu przeszukuje B, U i Z, których nie znaleziono.

char [] arr = nowy char [] 'd', „h”, „n”, „o”, „p”, „q”, „s”, „t”, „v”, „x” ;
int ret1 = tablice.BinarySearch (ARR, „B”);
int ret2 = tablice.BinarySearch (arr, „u”);
int ret3 = tablice.BinarySearch (ARR, „Z”);
System.na zewnątrz.druk (ret1); System.na zewnątrz.druk ("); system.na zewnątrz.druk (ret2);
System.na zewnątrz.druk ("); system.na zewnątrz.druk (RET3); System.na zewnątrz.wydrukować(");
System.na zewnątrz.println ();

Wyjście jest,

-1 -9-11

Wyszukiwanie zasięgu

Składnia do wyszukiwania szeregu znanych to:

public static int binarySearch (char [] a, int fromindex, int toindex, char key)

od indeksu jest normalny wskaźnik, w którym zaczyna się zakres. Toindex to normalny wskaźnik tuż po ostatnim elemencie zakresu. Poniższy segment kodu przeszukuje posortowaną tablicę od indeksu 3 do tuż po indeksie 7, czyli indeks 8. Element dla indeksu 8 nie jest uwzględniony w zakresie.

char [] arr = nowy char [] 'd', „h”, „n”, „o”, „p”, „q”, „s”, „t”, „v”, „x” ;
int ret = tablice.BinarySearch (ARR, 3, 8, „S”);
System.na zewnątrz.println (ret);

Kluczem jest s, a wyjście to 6.

Wniosek

Składnie tablic do wyszukiwania tablicy prymitywnych typów to:

• public static int binarySearch (bajt [] a, bajtowy klucz)
• public static int binarySearch (bajt [] a, int fromindex, int toindex, bajtowy klucz)
• public static int binarySearch (char [] a, char key)
• public static int binarySearch (char [] a, int fromindex, int toindex, char key)
• public static int binarySearch (double [] a, podwójny klucz)
• public static int binarySearch (double [] a, int fromindex, int toindex, podwójny klucz)
• public static int binarySearch (float [] a, float klucz)
• public static int binarySearch (float [] a, int fromindex, int toindex, float klucz)
• public static int binarySearch (int [] a, int klucz)
• public static int binarySearch (int [] a, int fromindex, int toindex, int klucz)