Algoritmii de căutare și sortare sunt algoritmi populari în orice limbaje de programare. Ele reprezintă baza pentru a înțelege fundamentele programării. Un astfel de algoritm de căutare popular este Binary Search in . În acest articol, vă voi spune totul despre implementarea acestuia.
Subiectele de mai jos sunt tratate în acest articol:
Să începem!
Ce este Binary Search?
Căutare binară în este o algoritm de căutare care găsește poziția unei valori țintă în cadrul unei sortări matrice . Căutare binară compară valoarea țintă cu elementul de mijloc al tabloului. Aceastafuncționează numai pe un set sortat de elemente. Pentru a utiliza căutarea binară într-o colecție, trebuie mai întâi sortate.
Cand este folosit pentru a efectua operațiuni pe un set sortat, numărul de iterații poate fi întotdeauna redus pe baza valorii căutate. Puteți vedea în instantaneul de mai sus despre găsirea fișierului element mijlociu . Analogia căutării binare este de a utiliza informațiile în care este sortată matricea și de a reduce complexitatea timpului O (jurnal n) .
Implementarea algoritmului de căutare binară
Să aruncăm o privire la pseudo-codul de mai jos pentru a-l înțelege într-un mod mai bun.
Procedură binary_search A & larr sorted array n & larr size of array x & larr value to be search Set low = 1 Set high = n în timp ce x nu este găsit dacă este mareExplicaţie:
Pasul 1: În primul rând, comparați x cu elementul de mijloc.
Pasul 2: Dacă x se potrivește cu elementul de mijloc, atunci trebuie să returnați indexul mediu.
Pasul 3: Altfel, dacă x este mai mare decât elementul mijlociu, atunci x poate sta doar în jumătatea din dreapta după elementul mediu. Prin urmare, repeti jumătatea potrivită.
Pasul 4: Altfel, dacă (x este mai mic), repetați-vă pentru jumătatea stângă.
Așa trebuie să căutați elementul din matricea dată.
cum se creează o listă legată în cSă vedem acum cum să implementăm recursiv un algoritm de căutare binară. Programul de mai jos demonstrează același lucru.
Căutare binară recursivă
public class BinarySearch {// Implementarea Java a recursive Binary Search // Returnează indexul lui x dacă este prezent în arr [l..h], altfel returnează -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Dacă elementul este prezent chiar la mijloc if (a [mid] == x) returnează mid // If element este mai mic decât mid, atunci poate fi prezent doar în subarray stâng dacă (a [mid]> x) returnează binarySearch (arr, l, mid - 1, x) // Altfel elementul poate fi prezent doar în subarray dreapta returnează binarySearch (arr, mid + 1, h, x)} // Ajungem aici când elementul nu este prezent în returul matricei -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a.length int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Element neprezentat') else System.out.println ('Element găsit la index' + res)}}La executarea programului de mai sus, acesta va localiza elementul prezent la indexul particular
Element găsit la indexul 2Deci, acest lucru ne aduce la sfârșitul Căutării binare în Java articol. Sper că l-ați găsit informativ și v-ați ajutat la înțelegere .
Verificați de Edureka, o companie de învățare online de încredere, cu o rețea de peste 250.000 de elevi mulțumiți răspândiți pe tot globul. Suntem aici pentru a vă ajuta cu fiecare pas din călătoria dvs., pentru a deveni un în afară de aceste întrebări de interviu java. Venim cu un curriculum care este conceput pentru studenți și profesioniști care doresc să fie dezvoltator Java. Cursul este conceput pentru a vă oferi un început avansat în programarea Java și pentru a vă instrui atât pentru conceptele Java de bază, cât și pentru cele avansate, împreună cu diverse cadre Java, cum ar fi Hibernate & Spring.
În cazul în care vă confruntați cu dificultăți în timpul implementării Căutării binare în , vă rugăm să o menționați în secțiunea de comentarii de mai jos și ne vom întoarce cel mai devreme.