Binært søk er en av søketeknikkene som brukes når inndata sorteres her, vi fokuserer på å finne det midterste elementet som fungerer som en referanseramme om det skal gå til venstre eller høyre til det siden elementene allerede er sortert. Dette søket hjelper til med å optimere søketeknikken med hver iterasjon, omtales som binært søk, og leserne legger vekt på det da det indirekte brukes til å løse spørsmål.
Binær søkealgoritme i Java
Nedenfor er algoritmen designet for binært søk:
- Start
- Ta input array og Target
- Initialiser start = 0 og slutt = (matrisestørrelse -1)
- Indianiser mellomvariabel
- mid = (start+slutt)/2
- hvis array[ mid ] == mål så returner midten
- if array[ mid ]
- hvis array[ mid ]> target så slutt = mid-1
- hvis start<=slutt, gå til trinn 5
- returner -1 som Ikke-element funnet
- Exit
Nå må du tenke på hva hvis inndataene ikke er sortert, så er resultatene udefinerte.
Merk: Hvis det er duplikater, er det ingen garanti for hvilken som blir funnet.
Metoder for Java binært søk
Det er tre metoder i Java å implementere Binært søk i Java er nevnt nedenfor:
- Iterativ metode
- Rekursiv metode
- Innbygget metode
1. Iterativ metode for binært søk i Java
Nedenfor er implementeringen nevnt nedenfor:
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);> >}> }> |
>
>Produksjon
rekursjon i java
Element found at index 3>
Tips: Geeks du må lure på om det er noen funksjon som nedre_grense() eller øvre grense() sannsynligvis funnet i C++ STL. så det rette svaret er at det ikke var noen funksjon bare før Java 9, senere ble de lagt til.
2. Rekursiv metode for binært søk
Nedenfor er implementeringen av metoden ovenfor:
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);> >}> }> |
>
>Produksjon
Element is present at index 3>
Kompleksiteten til metoden ovenfor
Tidskompleksitet: O(log N)
Plass kompleksitet: O(1), Hvis den rekursive anropsstakken vurderes, vil hjelperommet være O(log N)
3. I byggemetode for binært søk i Java
Arrays.binarysearch() fungerer for arrays som også kan være av primitiv datatype.
Nedenfor er implementeringen av metoden ovenfor:
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'>);> >}> }> |
>
>Produksjon
22 found at index = 3 40 Not found>
Binært søk i Java-samlinger
La oss nå se hvordan Collections.binarySearch() fungerer for LinkedList. Så i utgangspunktet, som diskutert ovenfor, kjører denne metoden i log(n)-tid for en tilfeldig tilgangsliste som ArrayList. Hvis den angitte listen ikke implementerer RandomAccess-grensesnittet og er stor, vil denne metoden gjøre et iteratorbasert binært søk som utfører O(n)-koblingsgjennomganger og O(log n)-elementsammenlikninger.
Collections.binarysearch() fungerer for objekter Samlinger som ArrayList og LinkedList .
Nedenfor er implementeringen av metoden ovenfor:
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'>);> >}> }> |
>
>Produksjon
10 found at index = 3 15 Not found>
Kompleksiteten til metoden ovenfor
Tidskompleksitet : O(log N)
Hjelpeplass : O(1)