Binair zoeken is een van de zoektechnieken die worden toegepast wanneer de invoer wordt gesorteerd. Hier concentreren we ons op het vinden van het middelste element dat als referentiekader fungeert, of we er nu links of rechts naartoe moeten gaan, aangezien de elementen al zijn gesorteerd. Dit zoeken helpt bij het optimaliseren van de zoektechniek, waarbij elke iteratie binair zoeken wordt genoemd en lezers benadrukken dit omdat het indirect wordt toegepast bij het oplossen van vragen.
Binair zoekalgoritme in Java
Hieronder vindt u het algoritme dat is ontworpen voor binair zoeken:
- Begin
- Neem invoerarray en Target
- Initialiseer start = 0 en einde = (arraygrootte -1)
- Indianize middenvariabele
- midden = (begin+einde)/2
- if array[ mid ] == doel retourneer dan mid
- if array[ midden ]
- als array[ mid ]> doel dan end = mid-1
- als start<=einde ga dan naar stap 5
- retourneer -1 als Niet element gevonden
- Uitgang
Nu moet u zich afvragen: als de invoer niet is gesorteerd, zijn de resultaten ongedefinieerd.
Opmerking: Als er duplicaten zijn, is er geen garantie welke zal worden gevonden.
Methoden voor binair zoeken in Java
Er zijn drie methoden in Java om te implementeren Binaire zoekopdracht in Java worden hieronder vermeld:
- Iteratieve methode
- Recursieve methode
- Ingebouwde methode
1. Iteratieve methode voor binair zoeken in Java
Hieronder wordt de implementatie hieronder vermeld:
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);> >}> }> |
>
>Uitvoer
nfa naar dfa
Element found at index 3>
Tip: Geeks, je vraagt ​​je vast af of er een functie is zoals ondergrens() of bovengrens() waarschijnlijk gevonden in C++ STL. dus het duidelijke antwoord is dat er pas tot Java 9 een functie was, later werden ze toegevoegd.
2. Recursieve methode voor binair zoeken
Hieronder vindt u de implementatie van de bovenstaande methode:
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);> >}> }> |
>
>Uitvoer
Element is present at index 3>
Complexiteit van de bovenstaande methode
Tijdcomplexiteit: O(log N)
Ruimtecomplexiteit: O(1), als de recursieve call-stack in aanmerking wordt genomen, zal de hulpruimte O(log N) zijn
3. In build-methode voor binair zoeken in Java
Arrays.binarysearch() werkt voor arrays die ook van een primitief gegevenstype kunnen zijn.
Hieronder vindt u de implementatie van de bovenstaande methode:
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'>);> >}> }> |
>
>Uitvoer
22 found at index = 3 40 Not found>
Binair zoeken in Java-collecties
Laten we nu eens kijken hoe Collections.binarySearch() werkt voor LinkedList. Dus, zoals hierboven besproken, draait deze methode in log(n)-tijd voor een willekeurige toegangslijst zoals ArrayList. Als de opgegeven lijst de RandomAccess-interface niet implementeert en groot is, voert deze methode een op iterator gebaseerde binaire zoekopdracht uit die O(n)-linktraversals en O(log n)-elementvergelijkingen uitvoert.
Collecties.binarysearch() werkt voor objecten Collecties zoals ArrayLijst En GelinkteLijst .
Hieronder vindt u de implementatie van de bovenstaande methode:
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'>);> >}> }> |
>
>Uitvoer
10 found at index = 3 15 Not found>
De complexiteit van de bovenstaande methode
Tijdcomplexiteit : O(log N)
Hulpruimte : O(1)