Algorytm wyszukiwania binarnego w Javie

binary search algorithm java implementation examples

W tym samouczku wyjaśniono wyszukiwanie binarne i rekurencyjne wyszukiwanie binarne w języku Java wraz z algorytmem, implementacją i przykładami kodu binarnego wyszukiwania w języku Java:

Wyszukiwanie binarne w języku Java to technika używana do wyszukiwania docelowej wartości lub klucza w kolekcji. Jest to technika wykorzystująca technikę „dziel i rządź” w celu znalezienia klucza.

Zbiór, dla którego ma być zastosowane wyszukiwanie binarne w celu wyszukania klucza, musi być posortowany w kolejności rosnącej.

Zwykle większość języków programowania obsługuje wyszukiwanie liniowe, wyszukiwanie binarne i techniki mieszania, które są używane do wyszukiwania danych w kolekcji. Dowiemy się haszowania w naszych kolejnych samouczkach.

=> Odwiedź tutaj, aby nauczyć się języka Java od podstaw.

Czego się nauczysz:

Wyszukiwanie binarne w Javie
Wniosek
- rekomendowane lektury

Wyszukiwanie binarne w Javie

Wyszukiwanie liniowe to podstawowa technika. W tej technice tablica jest przechodzona sekwencyjnie, a każdy element jest porównywany z kluczem, aż do znalezienia klucza lub osiągnięcia końca tablicy.

Wyszukiwanie liniowe jest rzadko używane w praktycznych zastosowaniach. Wyszukiwanie binarne jest najczęściej używaną techniką, ponieważ jest znacznie szybsze niż wyszukiwanie liniowe.

Java udostępnia trzy sposoby wyszukiwania binarnego:

Stosowanie podejścia iteracyjnego
Korzystanie z podejścia rekurencyjnego
Korzystanie z metody Arrays.binarySearch ().

W tym samouczku zaimplementujemy i omówimy wszystkie te 3 metody.

W metodzie wyszukiwania binarnego kolekcja jest wielokrotnie dzielona na pół, a element kluczowy jest przeszukiwany w lewej lub prawej połowie kolekcji w zależności od tego, czy klucz jest mniejszy lub większy niż środkowy element kolekcji.

Prosty algorytm wyszukiwania binarnego jest następujący:

Oblicz środkowy element kolekcji.
Porównaj kluczowe elementy z elementem środkowym.
Jeśli klucz = środkowy element, zwracamy środkową pozycję indeksu dla znalezionego klucza.
W przeciwnym razie Jeśli klucz> środkowy element, to klucz leży w prawej połowie zbioru. Dlatego powtórz kroki od 1 do 3 w dolnej (prawej) połowie zbioru.
W przeciwnym razie klucz

Jak widać z powyższych kroków, w wyszukiwaniu binarnym połowa elementów w kolekcji jest ignorowana tuż po pierwszym porównaniu.

Zauważ, że ta sama sekwencja kroków obowiązuje dla iteracyjnego i rekurencyjnego wyszukiwania binarnego.

Zilustrujmy algorytm wyszukiwania binarnego na przykładzie.

Na przykład, weź następującą posortowaną tablicę 10 elementów.

Obliczmy środkowe położenie tablicy.

Mid = 0 + 9/2 = 4

najlepsze darmowe narzędzie do naprawy systemu Windows 7

# 1) Klucz = 21

Najpierw porównamy wartość klucza z elementem [mid] i stwierdzimy, że wartość elementu w pozycji mid = 21.

W ten sposób znajdujemy klucz = [mid]. Stąd klucz znajduje się na pozycji 4 w tablicy.

# 2) Klucz = 25

Najpierw porównujemy wartość klucza z wartością mid. Jak (21<25), we will directly search for the key in the upper half of the array.

Teraz znowu znajdziemy środek górnej połowy tablicy.

Środek = 4 + 9/2 = 6

Wartość w miejscu [mid] = 25

Teraz porównujemy kluczowy element z elementem środkowym. Zatem (25 == 25), stąd znaleźliśmy klucz w lokalizacji [mid] = 6.

W ten sposób wielokrotnie dzielimy tablicę i porównując element kluczowy ze środkiem, decydujemy, w której połowie szukać klucza. Wyszukiwanie binarne jest bardziej wydajne pod względem czasu i poprawności, a także znacznie szybsze.

Implementacja wyszukiwania binarnego Java

Korzystając z powyższego algorytmu, zaimplementujmy program wyszukiwania binarnego w Javie przy użyciu podejścia iteracyjnego. W tym programie bierzemy przykładową tablicę i wykonujemy wyszukiwanie binarne w tej tablicy.

import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray[mid] last ){ System.out.println('Element is not found!'); } } }

Wynik:

Tablica wejściowa: [5, 10, 15, 20, 25, 30, 35]
Klucz do wyszukania = 20
Element znajduje się pod indeksem: 3

reszta pytań do wywiadu i odpowiedzi dla doświadczonych

Powyższy program przedstawia iteracyjne podejście do wyszukiwania binarnego. Najpierw deklarowana jest tablica, a następnie definiowany jest klucz do przeszukania.

Po obliczeniu środka tablicy klucz jest porównywany z elementem środkowym. Następnie, w zależności od tego, czy klucz jest mniejszy lub większy od klucza, klucz jest przeszukiwany odpowiednio w dolnej lub górnej połowie tablicy.

Rekurencyjne wyszukiwanie binarne w Javie

Możesz również przeprowadzić wyszukiwanie binarne przy użyciu techniki rekurencyjnej. Tutaj metoda wyszukiwania binarnego jest wywoływana rekurencyjnie do momentu znalezienia klucza lub wyczerpania całej listy.

Program implementujący rekurencyjne wyszukiwanie binarne jest podany poniżej:

import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray[], int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //if intArray[mid] > key then key is in left half of array if (intArray[mid] > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args[]){ //define array and key int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } }

Wynik:

Lista danych wejściowych: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Klucz do przeszukania:
Klucz znajduje się w lokalizacji: 3 na liście

Korzystanie z metody Arrays.binarySearch ().

Klasa Arrays w Javie udostępnia metodę „binarySearch ()”, która przeprowadza wyszukiwanie binarne w danej tablicy. Ta metoda przyjmuje tablicę i klucz do przeszukania jako argumenty i zwraca pozycję klucza w tablicy. Jeśli klucz nie zostanie znaleziony, metoda zwraca -1.

Poniższy przykład implementuje metodę Arrays.binarySearch ().

import java.util.Arrays; class Main{ public static void main(String args[]){ //define an array int intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } }

Wynik:

Tablica wejściowa: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Klucz do przeszukania: 50
Klucz znajduje się pod indeksem: 4 w tablicy.

Często Zadawane Pytania

Pytanie 1) Jak piszesz wyszukiwanie binarne?

Odpowiedź: Wyszukiwanie binarne jest zwykle wykonywane przez podzielenie tablicy na połowy. Jeśli klucz do przeszukania jest większy niż element środkowy, to górna połowa tablicy jest przeszukiwana przez dalsze dzielenie i przeszukiwanie podtablicy, aż do znalezienia klucza.

przykład dla abstrakcyjnego interfejsu w java

Podobnie, jeśli klucz jest mniejszy niż element środkowy, klucz jest przeszukiwany w dolnej połowie tablicy.

P # 2) Gdzie jest używane wyszukiwanie binarne?

Odpowiedź: Wyszukiwanie binarne jest używane głównie do wyszukiwania posortowanych danych w aplikacjach, zwłaszcza gdy przestrzeń pamięci jest niewielka i ograniczona.

P # 3) Jakie jest największe O w wyszukiwaniu binarnym?

Odpowiedź: Złożoność czasowa wyszukiwania binarnego wynosi O (logn), gdzie n to liczba elementów w tablicy. Przestrzenna złożoność wyszukiwania binarnego wynosi O (1).

Pytanie 4) Czy wyszukiwanie binarne jest rekurencyjne?

Odpowiedź: Tak. Ponieważ wyszukiwanie binarne jest przykładem strategii dziel i rządź i można je zaimplementować za pomocą rekurencji. Możemy podzielić tablicę na połowy i wywołać tę samą metodę, aby wielokrotnie wyszukiwać binarnie.

P # 5) Dlaczego nazywa się to wyszukiwaniem binarnym?

Odpowiedź: Algorytm wyszukiwania binarnego wykorzystuje strategię dziel i rządź, która wielokrotnie dzieli tablicę na połowy lub dwie części. Dlatego nazywa się to wyszukiwaniem binarnym.

Wniosek

Wyszukiwanie binarne jest często używaną techniką wyszukiwania w Javie. Warunkiem przeprowadzenia wyszukiwania binarnego jest sortowanie danych w kolejności rosnącej.

Wyszukiwanie binarne można zaimplementować przy użyciu podejścia iteracyjnego lub rekurencyjnego. Klasa Arrays w Javie udostępnia również metodę „binarySearch”, która przeprowadza wyszukiwanie binarne w tablicy Array.

W naszych kolejnych samouczkach poznamy różne techniki sortowania w Javie.

=> Obejrzyj serię prostych szkoleń dotyczących języka Java.

Algorytm wyszukiwania binarnego w Javie - implementacja i przykłady

Wyszukiwanie binarne w Javie