La búsqueda binaria es una de las técnicas de búsqueda que se aplican cuando la entrada está ordenada. Aquí nos centramos en encontrar el elemento central que actúa como marco de referencia, ya sea para ir hacia la izquierda o hacia la derecha, ya que los elementos ya están ordenados. Esta búsqueda ayuda a optimizar la técnica de búsqueda con cada iteración y se denomina búsqueda binaria y los lectores se preocupan por ella, ya que se aplica indirectamente para resolver preguntas.
Algoritmo de búsqueda binaria en Java
A continuación se muestra el algoritmo diseñado para la búsqueda binaria:
- Comenzar
- Tome la matriz de entrada y el objetivo
- Inicializar inicio = 0 y final = (tamaño de matriz -1)
- Indianizar variable media
- medio = (inicio+fin)/2
- si matriz [mid] == objetivo, entonces regresa mid
- si matriz [mediados]
- si matriz[mid]> objetivo entonces final = mid-1
- Si inicio <= fin, vaya al paso 5
- devolver -1 como elemento no encontrado
- Salida
Ahora debes estar pensando qué pasa si la entrada no está ordenada, entonces los resultados no están definidos.
Nota: Si hay duplicados, no hay garantía de cuál se encontrará.
Métodos para la búsqueda binaria de Java
Hay tres métodos en Java para implementar. Búsqueda binaria en Java se mencionan a continuación:
- Método iterativo
- Método recursivo
- Método incorporado
1. Método iterativo para búsqueda binaria en Java
A continuación se muestra la implementación que se menciona a continuación:
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);> >}> }> |
>
>Producción
listas java
Element found at index 3>
Consejo: Geeks, deben preguntarse si existe alguna función como límite inferior() o límite_superior() Probablemente se encuentre en C++ STL. Entonces, la respuesta directa es que no hubo ninguna función solo hasta Java 9, más tarde se agregaron.
2. Método recursivo para búsqueda binaria
A continuación se muestra la implementación del método anterior:
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);> >}> }> |
>
>Producción
Element is present at index 3>
Complejidad del método anterior.
Complejidad del tiempo: O(logN)
Complejidad espacial: O (1), si se considera la pila de llamadas recursiva, entonces el espacio auxiliar será O (log N)
3. En método de compilación para búsqueda binaria en Java
Arrays.binarysearch() Funciona para matrices que también pueden ser de tipo de datos primitivos.
A continuación se muestra la implementación del método anterior:
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'>);> >}> }> |
>
>Producción
22 found at index = 3 40 Not found>
Búsqueda binaria en colecciones de Java
Ahora veamos cómo funciona Collections.binarySearch() para LinkedList. Básicamente, como se analizó anteriormente, este método se ejecuta en tiempo log(n) para una lista de acceso aleatorio como ArrayList. Si la lista especificada no implementa la interfaz RandomAccess y es grande, este método realizará una búsqueda binaria basada en iteradores que realiza recorridos de enlaces O(n) y comparaciones de elementos O(log n).
Colecciones.binarysearch() funciona para colecciones de objetos como Lista de arreglo y Lista enlazada .
A continuación se muestra la implementación del método anterior:
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'>);> >}> }> |
>
>Producción
10 found at index = 3 15 Not found>
La complejidad del método anterior.
Complejidad del tiempo : O(logN)
Espacio auxiliar :O(1)