Binārā meklēšana ir viens no meklēšanas paņēmieniem, ko izmanto, kad ievade tiek kārtota. Šeit mēs koncentrējamies uz vidējā elementa atrašanu, kas darbojas kā atsauces rāmis, vai doties uz to pa kreisi vai pa labi, jo elementi jau ir sakārtoti. Šī meklēšana palīdz optimizēt meklēšanas paņēmienus katrā iterācijā, ko sauc par bināro meklēšanu, un lasītāji to uztrauc, jo to netieši izmanto jautājumu risināšanā.
Binārās meklēšanas algoritms Java
Zemāk ir algoritms, kas paredzēts binārajai meklēšanai:
- Sākt
- Paņemiet ievades masīvu un Target
- Inicializēt sākums = 0 un beigas = (masīva izmērs -1)
- Indiānizēts vidējais mainīgais
- vidus = (sākums+beigas)/2
- if array[ mid ] == target, then return mid
- ja masīvs [ vidus ]
- ja masīvs[ vidusdaļa ]> mērķis, tad beigas = vidus-1
- ja sākums<=beigas, tad pārejiet pie 5. darbības
- atgriezt -1 kā Elements nav atrasts
- Izeja
Tagad jums jādomā, kā rīkoties, ja ievade nav sakārtota, tad rezultāti nav definēti.
Piezīme: Ja ir dublikāti, nav garantijas, kurš tiks atrasts.
Java binārās meklēšanas metodes
Java ir trīs ieviešanas metodes Binārā meklēšana Java valodā ir minēti zemāk:
- Iteratīvā metode
- Rekursīvā metode
- Iebūvēšanas metode
1. Iteratīvā metode binārajai meklēšanai Java
Tālāk ir norādīta ieviešana:
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);> >}> }> |
>
>Izvade
kartēšana mašīnrakstā
Element found at index 3>
Padoms: Geeks jums noteikti ir jautājums, vai ir kāda funkcija, piemēram apakšējā_ robeža() vai augšējā_ robeža() tikai, iespējams, atrodams C++ STL. tātad tieša atbilde ir tāda, ka tikai līdz Java 9 nebija nevienas funkcijas, vēlāk tās tika pievienotas.
2. Rekursīvā metode binārajai meklēšanai
Zemāk ir aprakstīta iepriekš minētās metodes ieviešana:
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);> >}> }> |
>
>Izvade
Element is present at index 3>
Iepriekš minētās metodes sarežģītība
Laika sarežģītība: O(log N)
Kosmosa sarežģītība: O(1), ja tiek ņemta vērā rekursīvā izsaukuma steka, tad palīgtelpa būs O(log N)
3. Sadaļā Build Method for Binary Search Java
Arrays.binarysearch() darbojas masīviem, kuriem var būt arī primitīvs datu tips.
Zemāk ir aprakstīta iepriekš minētās metodes ieviešana:
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'>);> >}> }> |
>
>Izvade
22 found at index = 3 40 Not found>
Binārā meklēšana Java kolekcijās
Tagad apskatīsim, kā Collections.binarySearch() darbojas LinkedList. Tātad, kā minēts iepriekš, šī metode darbojas žurnāla (n) laikā brīvpiekļuves sarakstam, piemēram, ArrayList. Ja norādītajā sarakstā nav ieviesta RandomAccess saskarne un tas ir liels, šī metode veiks uz iteratoru balstītu bināro meklēšanu, kas veic O(n) saišu pārvietošanos un O(log n) elementu salīdzināšanu.
Collections.binarysearch() darbojas objektiem Kolekcijas, piemēram ArrayList un LinkedList .
Zemāk ir aprakstīta iepriekš minētās metodes ieviešana:
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'>);> >}> }> |
>
>Izvade
10 found at index = 3 15 Not found>
Iepriekš minētās metodes sarežģītība
Laika sarežģītība : O(log N)
Palīgtelpa : O(1)