Algorytm wyszukiwania binarnego w Javie

binary search algorithm java implementation examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Wybierz System Operacyjny Wybierz Program Projekcji (Opcjonalnie)

Opisz Swój Problem

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:

najlepsze darmowe narzędzie do naprawy systemu Windows 7

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

# 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

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.

reszta pytań do wywiadu i odpowiedzi dla doświadczonych

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