La ricerca binaria è una delle tecniche di ricerca applicate quando l'input viene ordinato: qui ci concentriamo sulla ricerca dell'elemento centrale che funge da quadro di riferimento se andare a sinistra o a destra poiché gli elementi sono già ordinati. Questa ricerca aiuta a ottimizzare la tecnica di ricerca con ogni iterazione, viene definita ricerca binaria e i lettori ne sottolineano l'importanza poiché viene applicata indirettamente nella risoluzione delle domande.
Algoritmo di ricerca binaria in Java
Di seguito è riportato l'algoritmo progettato per la ricerca binaria:
- Inizio
- Prendi l'array di input e Target
- Inizializza start = 0 e end = (dimensione array -1)
- Indianizzare la variabile media
- metà = (inizio+fine)/2
- se array[ mid ] == target allora ritorna mid
- if array[ metà ]
- se array[mid]> target allora end = mid-1
- se inizio<=fine vai al passaggio 5
- restituisce -1 come elemento non trovato
- Uscita
Ora devi pensare che cosa accadrebbe se l'input non fosse ordinato, i risultati sarebbero indefiniti.
Nota: Se sono presenti duplicati, non vi è alcuna garanzia su quale verrà trovato.
Metodi per la ricerca binaria Java
Esistono tre metodi in Java da implementare Ricerca binaria in Java sono menzionati di seguito:
- Metodo iterativo
- Metodo ricorsivo
- Metodo integrato
1. Metodo iterativo per la ricerca binaria in Java
Di seguito è riportata l'implementazione menzionata di seguito:
Giava
// 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);> >}> }> |
>
>Produzione
java switch int
Element found at index 3>
Mancia: Geek, ti starai chiedendo se esiste una funzione simile limite inferiore() O limite superiore() probabilmente trovato in C++ STL. quindi la risposta diretta è che non esistevano funzioni solo fino a Java 9, poi sono state aggiunte in seguito.
2. Metodo ricorsivo per la ricerca binaria
Di seguito è riportata l'implementazione del metodo sopra:
Giava
// 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);> >}> }> |
>
>Produzione
Element is present at index 3>
Complessità del metodo sopra
Complessità temporale: O(logN)
Complessità spaziale: O(1), Se viene considerato lo stack di chiamate ricorsivo, lo spazio ausiliario sarà O(log N)
3. Metodo di compilazione per la ricerca binaria in Java
Array.binarysearch() funziona anche per array che possono essere di tipo dati primitivo.
Di seguito è riportata l'implementazione del metodo sopra:
Giava
// 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'>);> >}> }> |
>
>Produzione
22 found at index = 3 40 Not found>
Ricerca binaria nelle raccolte Java
Ora vediamo come funziona Collections.binarySearch() per LinkedList. Quindi, in pratica, come discusso sopra, questo metodo viene eseguito in tempo log(n) per un elenco di accesso casuale come ArrayList. Se l'elenco specificato non implementa l'interfaccia RandomAccess ed è di grandi dimensioni, questo metodo eseguirà una ricerca binaria basata su iteratori che esegue attraversamenti di collegamenti O(n) e confronti di elementi O(log n).
Collezioni.binarysearch() funziona per collezioni di oggetti come Lista di array E Lista collegata .
Di seguito è riportata l'implementazione del metodo sopra:
Giava
// 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'>);> >}> }> |
>
>Produzione
10 found at index = 3 15 Not found>
La complessità del metodo di cui sopra
Complessità temporale : O(logN)
Spazio ausiliario : O(1)