Arrays.binarySearch() El método busca en la matriz especificada del tipo de datos dado el valor especificado utilizando el algoritmo de búsqueda binaria. La matriz debe ordenarse según el matrices.sort() método antes de realizar esta llamada. Si no está ordenado, los resultados no están definidos. Si la matriz contiene varios elementos con el valor especificado, no hay garantía de cuál se encontrará. Repasemos la ilustración que se proporciona a continuación de la siguiente manera.
Ilustración:
Searching for 35 in byteArr[] = {10,20,15,22,35} will give result as 4 as it is the index of 35 Searching for g in charArr[] = {'g','p','q','c','i'} will give result as 0 as it is the index of 'g' Searching for 22 in intArr[] = {10,20,15,22,35}; will give result as 3 as it is the index of 22 Searching for 1.5 in doubleArr[] = {10.2,15.1,2.2,3.5} will give result as -1 as it is the insertion point of 1.5 Searching for 35.0 in floatArr[] = {10.2f,15.1f,2.2f,3.5f} will give result as -5 as it is the insertion point of 35.0 Searching for 5 in shortArr[] = {10,20,15,22,35} will give result as -1 as it is the insertion point of 5> Es el método más simple y eficiente para encontrar un elemento en una matriz ordenada en Java.
Sintaxis:
public static int binarySearch(data_type arr, data_type key)>
Recordar: Aquí el tipo de datos puede ser cualquiera de los tipos de datos primitivos, como byte, char, double, int, float, short, long e incluso object también.
Parámetros:
- La matriz a buscar
- El valor a buscar
Tipo de devolución: índice de la clave de búsqueda, si está contenida en la matriz; de lo contrario, (-(punto de inserción) – 1). El punto de inserción se define como el punto en el que la clave se insertaría en la matriz: el índice del primer elemento mayor que la clave, o a.length si todos los elementos de la matriz son menores que la clave especificada. Tenga en cuenta que esto garantiza que el valor de retorno será>= 0 si y sólo si se encuentra la clave.
Hay ciertos puntos importantes a tener en cuenta, como sigue:
- Si la lista de entrada no está ordenada, los resultados no están definidos.
- Si hay duplicados, no hay garantía de cuál se encontrará.
Como arriba ya hemos discutido que podemos operar este algoritmo ya sea Arrays.binarysearch() vs. Colecciones.binarysearch() . Arrays.binarysearch() funciona para matrices que también pueden ser de tipos de datos primitivos. Colecciones .binarysearch() funciona para colecciones de objetos como Lista de arreglo y Lista enlazada .
Ejemplo 1:
Java
cuerdas en c
// Java program to demonstrate working of Arrays.> // binarySearch() in a sorted array> // Importing Arrays class from> // java.util package> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring and initializing byte arrays> >// to search over them> >byte> byteArr[] = {>10>,>20>,>15>,>22>,>35> };> >char> charArr[] = {>'g'>,>'p'>,>'q'>,>'c'>,>'i'> };> >int> intArr[] = {>10>,>20>,>15>,>22>,>35> };> >double> doubleArr[] = {>10.2>,>15.1>,>2.2>,>3.5> };> >float> floatArr[] = {>10>.2f,>15>.1f,>2>.2f,>3>.5f };> >short> shortArr[] = {>10>,>20>,>15>,>22>,>35> };> >// Using sort() method of Arrays class> >// and passing arrays to be sorted as in arguments> >Arrays.sort(byteArr);> >Arrays.sort(charArr);> >Arrays.sort(intArr);> >Arrays.sort(doubleArr);> >Arrays.sort(floatArr);> >Arrays.sort(shortArr);> >// Primitive datatypes> >byte> byteKey =>35>;> >char> charKey =>'g'>;> >int> intKey =>22>;> >double> doubleKey =>1.5>;> >float> floatKey =>35>;> >short> shortKey =>5>;> >// Now in sorted array we will fetch and> >// return elements/indiciesaccessing indexes to show> >// array is really sorted> >// Print commands where we are implementing> >System.out.println(> >byteKey +>' found at index = '> >+ Arrays.binarySearch(byteArr, byteKey));> >System.out.println(> >charKey +>' found at index = '> >+ Arrays.binarySearch(charArr, charKey));> >System.out.println(> >intKey +>' found at index = '> >+ Arrays.binarySearch(intArr, intKey));> >System.out.println(> >doubleKey +>' found at index = '> >+ Arrays.binarySearch(doubleArr, doubleKey));> >System.out.println(> >floatKey +>' found at index = '> >+ Arrays.binarySearch(floatArr, floatKey));> >System.out.println(> >shortKey +>' found at index = '> >+ Arrays.binarySearch(shortArr, shortKey));> >}> }> |
>
>Producción
35 found at index = 4 g found at index = 1 22 found at index = 3 1.5 found at index = -1 35.0 found at index = -5 5 found at index = -1>
Análisis de complejidad:
Complejidad del tiempo:
La complejidad temporal del método Arrays.binarySearch() es O(log n) donde n es la longitud de la matriz de entrada. Esto se debe a que el método utiliza un algoritmo de búsqueda binaria para encontrar el elemento de destino en la matriz ordenada.
java para bucle
Espacio Auxiliar:
El espacio auxiliar utilizado por el método Arrays.binarySearch() es O(1), ya que no requiere ningún espacio adicional aparte de la matriz de entrada para realizar la operación de búsqueda.
Hay variantes de este método en las que también podemos especificar el rango de matriz en el que buscar. Hablaremos de eso, así como de la búsqueda en una matriz de objetos, en publicaciones posteriores.
Ejemplo 2:
Java
constante java
// Java Program to Illustrate 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 empty List> >List al =>new> ArrayList();> >// Adding elements to the List> >al.add(>12>);> >al.add(>53>);> >al.add(>23>);> >al.add(>46>);> >al.add(>54>);> >// Using binarySearch() method of Collections class> >// over random inserted element and storing the> >// index> >int> index = Collections.binarySearch(al,>23>);> >// Print and display the index> >System.out.print(index);> >}> }> |
>
>Producción
2>
Análisis de complejidad:
Complejidad del tiempo:
La complejidad temporal del método binarioSearch() en la clase Colecciones es O(log n) donde n es el número de elementos de la lista.
Espacio Auxiliar:
El método binarioSearch() en la clase Colecciones no requiere ningún espacio adicional y, por lo tanto, tiene una complejidad de espacio auxiliar de O(1).