Binárne vyhľadávanie je jednou z techník vyhľadávania, ktoré sa používajú pri triedení vstupu. Tu sa zameriavame na nájdenie stredného prvku, ktorý funguje ako referenčný rámec, či ísť doľava alebo doprava, pretože prvky sú už zoradené. Toto vyhľadávanie pomáha pri optimalizácii techniky vyhľadávania pri každej iterácii sa označuje ako binárne vyhľadávanie a čitatelia si naň kladú dôraz, pretože sa nepriamo používa pri riešení otázok.
Binárny vyhľadávací algoritmus v Jave
Nižšie je uvedený algoritmus navrhnutý pre binárne vyhľadávanie:
- Štart
- Vezmite vstupné pole a cieľ
- Inicializujte začiatok = 0 a koniec = (veľkosť poľa -1)
- Indianize strednej premennej
- stred = (začiatok+koniec)/2
- if array[ mid ] == target then return mid
- ak pole [ stred ]
- ak pole[ stred]> cieľ, potom koniec = stred 1
- ak začiatok<=koniec, prejdite na krok 5
- vráti hodnotu -1 ako prvok nenájdený
- VÝCHOD
Teraz musíte premýšľať o tom, čo ak vstup nie je zoradený, potom sú výsledky nedefinované.
Poznámka: Ak existujú duplikáty, nie je zaručené, ktorý z nich sa nájde.
Metódy pre Java Binary Search
V Jave existujú tri spôsoby implementácie Binárne vyhľadávanie v Jave sú uvedené nižšie:
- Iteračná metóda
- Rekurzívna metóda
- Inbuild Method
1. Iteratívna metóda pre binárne vyhľadávanie v Jave
Nižšie je uvedená implementácia:
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);> >}> }> |
>
>Výkon
js pole
Element found at index 3>
Tip: Geekovia sa určite pýtate, či existuje nejaká funkcia ako nižšia hranica() alebo Horná hranica() pravdepodobne nájdený v C++ STL. takže priama odpoveď je, že žiadna funkcia neexistovala iba do Java 9, neskôr boli pridané.
2. Rekurzívna metóda pre binárne vyhľadávanie
Nižšie je uvedená implementácia vyššie uvedenej metódy:
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);> >}> }> |
>
>Výkon
Element is present at index 3>
Zložitosť vyššie uvedenej metódy
Časová zložitosť: O (log N)
Priestorová zložitosť: O(1), Ak sa berie do úvahy zásobník rekurzívnych hovorov, pomocný priestor bude O (log N)
3. V metóde zostavenia pre binárne vyhľadávanie v jazyku Java
Arrays.binarysearch() funguje pre polia, ktoré môžu byť tiež primitívneho dátového typu.
Nižšie je uvedená implementácia vyššie uvedenej metódy:
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'>);> >}> }> |
>
>Výkon
22 found at index = 3 40 Not found>
Binárne vyhľadávanie v kolekciách Java
Teraz sa pozrime, ako Collections.binarySearch() funguje pre LinkedList. Takže v podstate, ako je uvedené vyššie, táto metóda beží v log(n) čase pre zoznam s náhodným prístupom, ako je ArrayList. Ak zadaný zoznam neimplementuje rozhranie RandomAccess a je veľký, táto metóda vykoná binárne vyhľadávanie založené na iterátore, ktoré vykoná prechody odkazov O(n) a porovnania prvkov O(log n).
Collections.binarysearch() funguje pre objekty Zbierky ako ArrayList a LinkedList .
Nižšie je uvedená implementácia vyššie uvedenej metódy:
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'>);> >}> }> |
>
>Výkon
10 found at index = 3 15 Not found>
Zložitosť vyššie uvedenej metódy
Časová zložitosť : O (log N)
Pomocný priestor : O(1)