Binär sökning är en av de söktekniker som används när inmatningen sorteras här fokuserar vi på att hitta mittelementet som fungerar som en referensram om man ska gå åt vänster eller höger till det eftersom elementen redan är sorterade. Denna sökning hjälper till att optimera söktekniken med varje iteration kallas binär sökning och läsare stressar över det eftersom det indirekt används för att lösa frågor.
Binär sökalgoritm i Java
Nedan är algoritmen designad för binär sökning:
- Start
- Ta input array och Target
- Initialisera start = 0 och slut = (matrisstorlek -1)
- Indianisera mellanvariabel
- mitt = (start+slut)/2
- om array[ mid ] == mål återvänd sedan mitten
- om array[ mitten]
- om array[ mid ]> target så slut = mid-1
- om start<=slut gå till steg 5
- returnera -1 som Not element found
- Utgång
Nu måste du tänka på vad om indata inte sorteras så är resultaten odefinierade.
Notera: Om det finns dubbletter finns det ingen garanti för vilken som kommer att hittas.
Metoder för Java Binary Search
Det finns tre metoder att implementera i Java Binär sökning i Java nämns nedan:
- Iterativ metod
- Rekursiv metod
- Inbyggd metod
1. Iterativ metod för binär sökning i Java
Nedan nämns implementeringen nedan:
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
oj koncept
Element found at index 3>
Dricks: Nördar ni måste undra om det finns någon funktion som nedre_gräns() eller övre gräns() hittas troligen i C++ STL. så det raka svaret är att det inte fanns någon funktion bara förrän Java 9, senare lades de till.
2. Rekursiv metod för binär sökning
Nedan är implementeringen av ovanstående metod:
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>
Komplexiteten hos ovanstående metod
Tidskomplexitet: O(log N)
Utrymmes komplexitet: O(1), om den rekursiva anropsstacken beaktas kommer hjälputrymmet att vara O(log N)
3. I byggmetod för binär sökning i Java
Arrays.binarysearch() fungerar för arrayer som också kan vara av primitiv datatyp.
Nedan är implementeringen av ovanstående metod:
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ökning i Java-samlingar
Låt oss nu se hur Collections.binarySearch() fungerar för LinkedList. Så i princip, som diskuterats ovan, körs denna metod i log(n)-tid för en slumpmässig tillgångslista som ArrayList. Om den angivna listan inte implementerar RandomAccess-gränssnittet och är stor, kommer den här metoden att göra en iteratorbaserad binär sökning som utför O(n)-länktraversals och O(log n)-elementjämförelser.
Collections.binarysearch() fungerar för objekt Samlingar som ArrayList och Länkad lista .
Nedan är implementeringen av ovanstående metod:
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>
Komplexiteten hos ovanstående metod
Tidskomplexitet : O(log N)
Hjälputrymme : O(1)