La búsqueda binaria también se denomina búsqueda binaria (Búsqueda binaria), que es un método de búsqueda más eficiente. Sin embargo, la búsqueda binaria requiere que la tabla lineal adopte una estructura de almacenamiento secuencial y que los elementos de la tabla estén ordenados por palabras clave.
Ventajas y desventajas de la búsqueda binaria
La ventaja es que el número de comparaciones es menor, la velocidad de búsqueda es rápida y el rendimiento promedio es bueno;
La desventaja es que la tabla a buscar debe ser una tabla ordenada, y la inserción y eliminación son difíciles.
Por lo tanto, el método de búsqueda binaria es adecuado para listas ordenadas que no cambian con frecuencia pero buscan con frecuencia.
Condiciones de uso: La secuencia de búsqueda es una estructura secuencial y está en orden.
Proceso
Primero, suponiendo que los elementos de la tabla están ordenados en orden ascendente, compare la palabra clave registrada en el medio de la tabla con la palabra clave de búsqueda si las dos son iguales. , la búsqueda es exitosa; de lo contrario, la tabla se divide en dos subtablas, la delantera y la trasera, utilizando el registro de la posición intermedia. Si la clave del registro de la posición intermedia es mayor que la palabra clave de búsqueda, entonces la subtabla anterior. se busca más; de lo contrario, se busca más en la última subtabla. Repita el proceso anterior hasta encontrar un registro que cumpla con las condiciones, lo que hace que la búsqueda sea exitosa, o hasta que la subtabla no exista, en cuyo caso la búsqueda falla.
Usa un bucle para implementar la búsqueda binaria
clase pública BinarySearch {
public static void main(String[] args) {
// Genera una matriz aleatoria int[] array = suiji();
// Ordena la matriz aleatoria Arrays.sort(array);
System.out.println(" The la matriz aleatoria generada es: " + Arrays.toString(array));
System.out.println("El valor que se encontrará: ");
Entrada del escáner = nuevo escáner (System.in);
// Valor objetivo para la búsqueda int aim = input.nextInt();
// Utilice el método de búsqueda binaria int index = binarioSearch(array, aim) ;
System.out.println("La posición de índice del valor a encontrar: " + índice);
}
/** * Generar una matriz aleatoria*
* @return valor de retorno, devuelve una matriz aleatoria*/
private static int[] suiji() {
// random. nextInt (n)+m? Devuelve un número aleatorio int entre m y m+n-1 n = new Random().nextInt(6) + 5;
int[] array = new int[n? ];
// Recorre y asigna valores a la matriz for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt (100);
}
return array;
}
/** * ¿Búsqueda binaria?- --cyclic Implementación del método *
* @param array La matriz que se buscará* @param aim El valor que se buscará* @return valor de retorno, se devuelve el índice si tiene éxito, se devuelve -1 si falló */
private static int binarioSearch(int[] array, int aim) {
//El valor de índice mínimo de la matriz int left = 0;
//El valor de índice máximo de la matriz int right = array.length - 1;
int mid;
mientras (izquierda <= derecha) {
mid = (izquierda + derecha) / 2;
// Si el valor de búsqueda es menor que el valor medio, use la primera mitad de todo el rango de búsqueda como el nuevo rango de búsqueda si (aim < array[mid]) {
right = mid - 1;
p>//Si el valor de búsqueda es mayor que el valor medio, utilice la segunda mitad de todo el rango de búsqueda como nuevo rango de búsqueda} else if (aim > array[mid]) {
left = mid + 1;
// Si los datos de búsqueda son exactamente iguales al elemento del medio valor, devolver el índice del valor del elemento medio } else {
devolver m?
id;
}
}
return -1;
}}
Ejecutar demostración de resultados:
De los resultados de ejecución anteriores, sabemos que si los datos que se van a encontrar existen en la matriz, se generará el índice de los datos en la matriz; si no existe, se generará -1; es decir, se imprimirá -1. No existe en la matriz; de lo contrario, existe.
4. Utilice la recursividad para implementar la búsqueda binaria
clase pública BinarySearch2 {
public static void main(String[] args) {
// Generar una matriz aleatoria int[] array = suiji();
// Ordenar la matriz aleatoria Arrays.sort(array);
System.out.println (" La matriz aleatoria generada es: " + Arrays.toString(array));
System.out.println("El valor que se encontrará: ");
Entrada del escáner = new Scanner(System.in);
// Valor objetivo para la búsqueda int aim = input.nextInt();
// Utilice el método de búsqueda binaria int index = binarioSearch( array, aim , 0, array.length - 1);
System.out.println("La posición del índice del valor a encontrar: " + índice);
}
/** * Genera una matriz aleatoria* * @return valor de retorno, devuelve una matriz aleatoria*/
private static int[] suiji() {
// Random.nextInt(n)+m ?Devuelve un número aleatorio int entre m y m+n-1 n = new Random().nextInt(6) + 5;
int[] array = new int [n];
// Recorre y asigna valores a la matriz for (int i = 0; i < array.length; i++) {
array[i] = new Random( ).nextInt(100);
}
matriz de retorno;
}
/** * Búsqueda binaria --- Método recursivo * * @param array Matriz a buscar * @param aim ? Valor a buscar * @param left Valor mínimo a la izquierda * @param right Valor máximo a la derecha * @return Valor de retorno, el índice se devuelve en caso de éxito, -1 en caso de error */
private static int binarioSearch(int[] array, int aim, int left, int right) {
if (aim < array[left] || aim > array[ right]) {
return -1;
}
// Encuentra el valor medio int mid = ( izquierda + derecha) / 2;
if (matriz[mid] == apuntar) {
regresar mid;
} else if (matriz[mid] > aim) {
//Si el valor del medio es mayor que el valor que estás buscando, continúa la recursividad desde la mitad izquierda return binarioSearch(array, aim, left, mid - 1);
} else {
//Si el valor medio es menor que el valor que buscas, continúa desde la mitad derecha.
Retorno recursivo binarioSearch(array, aim, mid + 1, array.length-1);
}
}}
Ejecutar demostración de resultados:
Resumen:
En comparación con los bucles, la recursividad tiene un código más simple, pero consume más tiempo y espacio y es menos eficiente. En el estudio y trabajo real, elija utilizarlo según la situación. Por lo general, si usamos bucles para implementar código, siempre que no sea demasiado engorroso, elegimos implementarlo en un bucle ~