Căutarea binară este una dintre tehnicile de căutare aplicate atunci când intrarea este sortată aici, ne concentrăm pe găsirea elementului din mijloc care acționează ca un cadru de referință dacă să mergem la stânga sau la dreapta, deoarece elementele sunt deja sortate. Această căutare ajută la optimizarea tehnicii de căutare cu fiecare iterație este denumită căutare binară, iar cititorii fac accent pe aceasta, deoarece este aplicată indirect în rezolvarea întrebărilor.
Algoritm de căutare binar în Java
Mai jos este algoritmul conceput pentru căutare binară:
- start
- Luați matrice de intrare și țintă
- Inițializați începutul = 0 și finalul = (dimensiunea matricei -1)
- Indianizare variabilă medie
- mijloc = (început+sfârşit)/2
- if array[ mid ] == target, return mid
- dacă matrice[ mijlocul ]
- dacă array[ mid ]> target then end = mid-1
- dacă start<=end atunci treceți la pasul 5
- returnează -1 ca element nu a fost găsit
- Ieșire
Acum trebuie să vă gândiți ce dacă intrarea nu este sortată, atunci rezultatele sunt nedefinite.
Notă: Dacă există duplicate, nu există nicio garanție care va fi găsit.
Metode pentru căutarea binară Java
Există trei metode de implementat în Java Căutare binară în Java sunt menționate mai jos:
- Metoda iterativă
- Metoda recursiva
- Metoda Inbuild
1. Metodă iterativă pentru căutare binară în Java
Mai jos, implementarea este menționată mai jos:
Java
// Java implementation of iterative Binary Search> class> BinarySearch {> >// Returns index of x if it is present in arr[l....r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >while> (l <= r) {> >int> mid = (l + r) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x) {> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >// so we decrease our r pointer to mid - 1> >}>else> if> (arr[mid]>x) {> >r = mid ->1>;> >// Else the element can only be present> >// in right subarray> >// so we increase our l pointer to mid + 1> >}>else> {> >l = mid +>1>;> >}> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// Driver method to test above> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(>'Element not present'>);> >else> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>Ieșire
încercați catch catch java
Element found at index 3>
Bacsis: Geeks, trebuie să vă întrebați dacă există vreo funcție ca limita inferioară() sau limită superioară() probabil găsit în C++ STL. deci răspunsul direct este că nu a existat nicio funcție doar până la Java 9, mai târziu au fost adăugate.
2. Metoda recursiva pentru căutare binară
Mai jos este implementarea metodei de mai sus:
Java
// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> >// Returns index of x if it is present in arr[l..> >// r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >if> (r>= l) {> >int> mid = l + (r - l) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// main function> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(> >'Element is not present in array'>);> >else> >System.out.println(> >'Element is present at index '> + result);> >}> }> |
>
>Ieșire
Element is present at index 3>
Complexitatea metodei de mai sus
Complexitatea timpului: O(log N)
Complexitatea spațiului: O(1), Dacă se ia în considerare stiva de apeluri recursive, atunci spațiul auxiliar va fi O(log N)
3. În Build Method for Binary Search in Java
Arrays.binarysearch() funcționează pentru matrice care pot fi, de asemenea, de tip primitiv de date.
Mai jos este implementarea metodei de mai sus:
Java
// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring an integer array> >int> arr[] = {>10>,>20>,>15>,>22>,>35> };> >// Sorting the above array> >// using sort() method of Arrays class> >Arrays.sort(arr);> >int> key =>22>;> >int> res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>40>;> >res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Ieșire
22 found at index = 3 40 Not found>
Căutare binară în colecțiile Java
Acum să vedem cum funcționează Collections.binarySearch() pentru LinkedList. Deci, practic, așa cum sa discutat mai sus, această metodă rulează în timp de log(n) pentru o listă de acces aleatoriu precum ArrayList. Dacă lista specificată nu implementează interfața RandomAccess și este mare, această metodă va efectua o căutare binară bazată pe iterator care efectuează traversări de legături O(n) și comparații de elemente O(log n).
Collections.binarysearch() funcționează pentru obiecte Colecții ca ArrayList și LinkedList .
Mai jos este implementarea metodei de mai sus:
Java
// Java Program to Demonstrate Working of binarySearch()> // method of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty ArrayList of integer type> >List al =>new> ArrayList();> >// Populating the Arraylist> >al.add(>1>);> >al.add(>2>);> >al.add(>3>);> >al.add(>10>);> >al.add(>20>);> >// 10 is present at index 3> >int> key =>10>;> >int> res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>15>;> >res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Ieșire
10 found at index = 3 15 Not found>
Complexitatea metodei de mai sus
Complexitatea timpului : O(log N)
Spațiu auxiliar : O(1)