binary search algorithm java implementation examples
Acest tutorial va explica căutarea binară și căutarea binară recursivă în Java împreună cu algoritmul, implementarea și exemplele de cod binar de căutare Java:
O căutare binară în Java este o tehnică care este utilizată pentru a căuta o valoare sau o cheie vizate într-o colecție. Este o tehnică care folosește tehnica „împarte și cucerește” pentru a căuta o cheie.
Colecția pe care se aplică căutarea binară pentru a căuta o cheie trebuie să fie sortată în ordine crescătoare.
De obicei, majoritatea limbajelor de programare acceptă căutarea liniară, căutarea binară și tehnicile Hashing care sunt utilizate pentru a căuta date în colecție. Vom învăța hashing în tutorialele noastre ulterioare.
=> Vizitați aici pentru a afla Java de la zero.
Ce veți învăța:
Căutare binară în Java
Căutarea liniară este o tehnică de bază. În această tehnică, matricea este parcursă secvențial și fiecare element este comparat cu cheia până când cheia este găsită sau se ajunge la sfârșitul matricei.
Căutarea liniară este utilizată rar în aplicații practice. Căutarea binară este cea mai frecvent utilizată tehnică, deoarece este mult mai rapidă decât o căutare liniară.
Java oferă trei moduri de a efectua o căutare binară:
cel mai bun software gratuit de backup pentru Mac
- Folosind abordarea iterativă
- Folosind o abordare recursivă
- Folosind metoda Arrays.binarySearch ().
În acest tutorial, vom implementa și vom discuta despre toate aceste 3 metode.
Algoritm pentru căutare binară în Java
În metoda de căutare binară, colecția este împărțită în mod repetat în jumătate și elementul cheie este căutat în jumătatea stângă sau dreaptă a colecției, în funcție de faptul dacă cheia este mai mică sau mai mare decât elementul mijlociu al colecției.
Un algoritm simplu de căutare binară este următorul:
- Calculați elementul de mijloc al colecției.
- Comparați elementele cheie cu elementul mijlociu.
- Dacă cheia = element de mijloc, atunci returnăm poziția indexului mediu pentru cheia găsită.
- Altfel Dacă cheie> element mijlociu, atunci cheia se află în jumătatea dreaptă a colecției. Repetați astfel pașii de la 1 la 3 în jumătatea inferioară (dreapta) a colecției.
- Altă cheie
După cum puteți vedea din pașii de mai sus, în căutarea binară, jumătate din elementele din colecție sunt ignorate imediat după prima comparație.
Rețineți că aceeași secvență de pași este valabilă atât pentru căutarea binară iterativă, cât și pentru cea recursivă.
Să ilustrăm algoritmul de căutare binară folosind un exemplu.
De exemplu, luați următoarea matrice sortată de 10 elemente.
Să calculăm locația de mijloc a matricei.
Mijloc = 0 + 9/2 = 4
# 1) Cheie = 21
În primul rând, vom compara valoarea cheie cu elementul (mid) și vom constata că valoarea elementului la mid = 21.
Astfel găsim acea cheie = (mijloc). Prin urmare, cheia se găsește în poziția 4 din matrice.
# 2) Tasta = 25
Mai întâi comparăm valoarea cheie cu mijlocul. După cum (21<25), we will directly search for the key in the upper half of the array.
Acum, din nou, vom găsi mijlocul pentru jumătatea superioară a matricei.
Mijloc = 4 + 9/2 = 6
Valoarea la locație (mijloc) = 25
Acum comparăm elementul cheie cu elementul mijlociu. Deci (25 == 25), prin urmare am găsit cheia la locația (mid) = 6.
Astfel împărțim în mod repetat matricea și prin compararea elementului cheie cu mijlocul, decidem în ce jumătate să căutăm cheia. Căutarea binară este mai eficientă în ceea ce privește timpul și corectitudinea și este mult mai rapidă.
Implementarea căutării binare Java
Folosind algoritmul de mai sus, permiteți-ne să implementăm un program de căutare binară în Java folosind abordarea iterativă. În acest program, luăm un exemplu de matrice și efectuăm căutare binară pe această matrice.
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!'); } } } Ieșire:
Matricea de intrare: (5, 10, 15, 20, 25, 30, 35)
Cheie de căutat = 20
Elementul se găsește la index: 3
cum să declarați o listă legată în java
Programul de mai sus prezintă o abordare iterativă a căutării binare. Inițial, se declară o matrice, apoi este definită o cheie care trebuie căutată.
După calcularea mijlocului matricei, cheia este comparată cu elementul mijlociu. Apoi, în funcție de faptul dacă cheia este mai mică sau mai mare decât cheia, cheia este căutată în jumătatea inferioară sau superioară a tabloului respectiv.
Căutare binară recursivă în Java
De asemenea, puteți efectua o căutare binară utilizând tehnica recursivă. Aici, metoda de căutare binară este apelată recursiv până când se găsește cheia sau se epuizează întreaga listă.
Programul care implementează o căutare binară recursivă este dat mai jos:
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'); } } Ieșire:
Lista de intrări: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Cheia de căutat:
Cheia se găsește la locație: 3 în listă
unde este cheia de securitate a rețelei
Folosind metoda Arrays.binarySearch ().
Clasa Arrays în Java oferă o metodă „binarySearch ()” care efectuează căutarea binară pe matricea dată. Această metodă ia matricea și cheia de căutat ca argumente și returnează poziția cheii din matrice. Dacă cheia nu este găsită, atunci metoda returnează -1.
Exemplul de mai jos implementează metoda 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.'); } } Ieșire:
Matricea de intrare: (10, 20, 30, 40, 50, 60, 70, 80, 90)
Cheia de căutat: 50
Cheia se găsește la index: 4 în matrice.
întrebări frecvente
Q # 1) Cum scrieți o căutare binară?
Răspuns: Căutarea binară se efectuează de obicei prin împărțirea matricei în jumătăți. Dacă cheia care trebuie căutată este mai mare decât elementul de mijloc, atunci jumătatea superioară a matricei este căutată prin divizarea și căutarea sub-matricei până când cheia este găsită.
În mod similar, dacă cheia este mai mică decât elementul mijlociu, atunci cheia este căutată în jumătatea inferioară a matricei.
Q # 2) Unde este utilizată căutarea binară?
Răspuns: Căutarea binară este utilizată în principal pentru a căuta date sortate în aplicații software, mai ales atunci când spațiul de memorie este compact și limitat.
Î # 3) Care este marele O al căutării binare?
Răspuns: Complexitatea de timp a căutării binare este O (logn) unde n este numărul de elemente din matrice. Complexitatea spațială a căutării binare este O (1).
Q # 4) Căutarea binară este recursivă?
Răspuns: Da. Deoarece căutarea binară este un exemplu de strategie de divizare și cucerire și poate fi implementată folosind recursivitate. Putem împărți matricea în jumătăți și putem apela aceeași metodă pentru a efectua căutarea binară din nou și din nou.
Q # 5) De ce se numește căutare binară?
Răspuns: Algoritmul de căutare binară folosește o strategie de divizare și cucerire care taie în mod repetat matricea în jumătăți sau două părți. Astfel este numit ca căutare binară.
Concluzie
Căutarea binară este tehnica de căutare frecvent utilizată în Java. Cerința pentru efectuarea unei căutări binare este ca datele să fie sortate în ordine crescătoare.
O căutare binară poate fi implementată folosind o abordare iterativă sau recursivă. Clasa Arrays din Java oferă, de asemenea, metoda „binarySearch” care efectuează o căutare binară pe o matrice.
În tutorialele noastre ulterioare, vom explora diverse tehnici de sortare în Java.
=> Urmăriți aici seria de antrenament Java simplă.
Lectură recomandată
- Selecție Sortare în Java - Selecție Sortare Algoritm și exemple
- Sortare prin inserare în Java - Algoritm de sortare și exemple
- Arborele de căutare binară C ++: Implementarea și operațiile BST cu exemple
- Interfață Java și tutorial de clasă abstractă cu exemple
- Tutorial JAVA pentru începători: peste 100 de cursuri video Java practice
- Sortare cu bule în Java - Algoritmi de sortare Java și exemple de cod
- Tutorial Java String | Metode Java String cu exemple
- Ce este Java Vector | Tutorial Java Vector Class cu exemple