Binær søgning er en af de søgeteknikker, der anvendes, når input er sorteret her, vi fokuserer på at finde det midterste element, der fungerer som en referenceramme, om det skal gå til venstre eller højre til det, da elementerne allerede er sorteret. Denne søgning hjælper med at optimere søgeteknikken med hver iteration omtales som binær søgning, og læserne stresser over det, da det indirekte anvendes til at løse spørgsmål.
Binær søgealgoritme i Java
Nedenfor er algoritmen designet til binær søgning:
- Start
- Tag input array og Target
- Initialiser start = 0 og slut = (matrixstørrelse -1)
- Indianiser mellemvariabel
- mid = (start+slut)/2
- hvis array[ mid ] == mål, så returner midt
- hvis array[ mid ]
- hvis array[ mid ]> target så end = mid-1
- hvis start<=slut, så gå til trin 5
- returner -1 som Ikke-element fundet
- Afslut
Nu må du tænke, hvad hvis input ikke er sorteret, så er resultaterne udefinerede.
Bemærk: Hvis der er dubletter, er der ingen garanti for, hvilken der bliver fundet.
Metoder til Java binær søgning
Der er tre metoder i Java at implementere Binær søgning i Java er nævnt nedenfor:
- Iterativ metode
- Rekursiv metode
- Indbygget metode
1. Iterativ metode til binær søgning i Java
Nedenfor er implementeringen nævnt 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);> >}> }> |
>
>Produktion
rekursion i java
Element found at index 3>
Tip: Nørder, du må undre dig over, om der er nogen funktion som nedre grænse() eller øvre grænse() bare sandsynligvis fundet i C++ STL. så det klare svar er, at der kun var nogen funktion før Java 9, senere blev de tilføjet.
2. Rekursiv metode til binær søgning
Nedenfor er implementeringen af ovenstående metode:
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);> >}> }> |
>
>Produktion
Element is present at index 3>
Kompleksiteten af ovenstående metode
Tidskompleksitet: O(log N)
Rumkompleksitet: O(1), Hvis den rekursive opkaldsstak tages i betragtning, vil hjælperummet være O(log N)
3. I byggemetode til binær søgning i Java
Arrays.binarysearch() virker for arrays, som også kan være af primitiv datatype.
Nedenfor er implementeringen af ovenstående metode:
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'>);> >}> }> |
>
>Produktion
22 found at index = 3 40 Not found>
Binær søgning i Java-samlinger
Lad os nu se, hvordan Collections.binarySearch() fungerer for LinkedList. Så dybest set, som diskuteret ovenfor, kører denne metode i log(n) tid for en tilfældig adgangsliste som ArrayList. Hvis den angivne liste ikke implementerer RandomAccess-grænsefladen og er stor, vil denne metode udføre en iterator-baseret binær søgning, der udfører O(n)-linkgennemgange og O(log n)-elementsammenligninger.
Collections.binarysearch() virker til objekter Samlinger som ArrayList og LinkedList .
Nedenfor er implementeringen af ovenstående metode:
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'>);> >}> }> |
>
>Produktion
10 found at index = 3 15 Not found>
Kompleksiteten af ovenstående metode
Tidskompleksitet : O(log N)
Hjælpeplads : O(1)