Uno de los algoritmos más fundamentales en informática es el algoritmo de búsqueda binaria. Puede implementar la búsqueda binaria utilizando dos métodos: el método iterativo y el método recursivo. Si bien ambos métodos tienen la misma complejidad de tiempo, el método iterativo es mucho más eficiente en términos de complejidad de espacio.

El método iterativo tiene una complejidad espacial de O(1) en comparación con O (inicio de sesión) producido por el método recursivo. Entonces, ¿cómo puede implementar el algoritmo de búsqueda binaria utilizando el método iterativo en C, C++ y Python?

¿Qué es la búsqueda binaria?

La búsqueda binaria, también conocida como búsqueda de medio intervalo, búsqueda logarítmica o corte binario, es un algoritmo que busca y devuelve la posición de un elemento en una matriz ordenada. El elemento de búsqueda se compara con el elemento intermedio. Tomando el promedio de los límites inferior y superior, puede encontrar los elementos intermedios.

Si el elemento de búsqueda es mayor que el elemento del medio, significa que todos los elementos del lado izquierdo son más pequeños que el elemento de búsqueda. Entonces, el control se desplaza hacia el lado derecho de la matriz (si la matriz está en orden ascendente) al aumentar el límite inferior a la siguiente posición del elemento central.

instagram viewer

De manera similar, si el elemento de búsqueda es más pequeño que el elemento del medio, significa que todos los elementos del lado derecho son más grandes que el elemento de búsqueda. Entonces, el control se desplaza a la parte izquierda de la matriz al cambiar el límite superior a la posición anterior del elemento central.

Esto reduce drásticamente el número de comparaciones en comparación con implementación de búsqueda lineal donde allí el número de comparaciones es igual al número de elementos en el peor de los casos. Este método resulta muy útil para encontrar números en una guía telefónica o palabras en un diccionario.

He aquí una representación esquemática de la Algoritmo de búsqueda binaria:

Búsqueda binaria usando C

Siga estos pasos para implementar la búsqueda binaria usando C:

El código fuente completo del programa de búsqueda binaria usando C, C++, Java y Python está presente en este repositorio GitHub.

El programa define una función, búsqueda binaria(), que devuelve el índice del valor encontrado o -1 si no está presente:

#incluir <stdio.h>
En tbúsqueda binaria(En t arr[], En t tamaño_arr, En t número_de_búsqueda){
/*... */
}

La función funciona reduciendo iterativamente el espacio de búsqueda. Dado que la búsqueda binaria funciona en matrices ordenadas, puede calcular el medio que, de lo contrario, no tiene sentido. Puede pedirle al usuario una matriz ordenada o usar algoritmos de clasificación como Bubble o Selection sort.

El bajo y alto Las variables almacenan los índices que representan los límites del espacio de búsqueda actual. medio almacena el índice en el medio:

En t bajo = 0, alto = arr_size - 1, medio;

El principal mientras() loop reducirá el espacio de búsqueda. Si el valor del índice bajo llega a ser mayor que el índice alto, entonces el espacio de búsqueda se ha agotado, por lo que el valor no puede estar presente.

mientras (bajo <= alto) {
/* continúa... [1] */
 }
devolver-1;

Después de actualizar el punto medio al comienzo del ciclo, hay tres resultados posibles:

  1. Si el valor en el punto medio es el que estamos buscando, devuelve ese índice.
  2. Si el valor del punto medio es mayor que el que estamos buscando, reduzca el alto.
  3. Si el valor del punto medio es menor, aumente el mínimo. 
/* [1] ...continúa */
 medio = (bajo + (alto - bajo)) / 2;
if (arr[mid] == número_búsqueda)
devolver medio;
demássi (arr[mid] > buscar_número)
 alto = medio - 1;
demás
 bajo = medio + 1;

Pruebe la función con la entrada del usuario. Usar escanear() para obtener información desde la línea de comando, incluido el tamaño de la matriz, su contenido y un número para buscar:

En tprincipal(){
En t arr[100], i, arr_size, search_number;
 imprimirf("Introduzca el número de elementos: ");
 escanear("%d", &tamaño_arr);
 imprimirf("Por favor ingrese números: ");
para (i = 0; i < tamaño_arr; i++) {
 escanear("%d", &arr[yo]);
 }


imprimirf("Introduzca el número a buscar: ");
 escanear("%d", &número_búsqueda);


i = búsqueda binaria (arr, arr_size, search_number);


si (i==-1)
 imprimirf("Número no presente");
demás
 imprimirf("El número está presente en la posición %d", yo + 1);
devolver0;
}

Si encuentra el número, muestre su posición o índice; de ​​lo contrario, aparecerá un mensaje que indica que el número no está presente.

Búsqueda binaria usando C++

Puede convertir el programa C en un programa C++ importando el Flujo de salida de entrada y usar espacio de nombres estándar para evitar repetirlo varias veces a lo largo del programa.

#incluir <iostream>
usando espacio de nombresestándar;

Usar cout con operador de extracción << en lugar de imprimirf() y cine con operador de inserción >> en lugar de escanear() y su programa C++ está listo.

imprimirf("Introduzca el número de elementos: ");
cout <<"Introduzca el número de elementos: ";
escanear("%d", &tamaño_arr);
cine >> tamaño_arr;

Búsqueda binaria usando Python

Como Python no tiene soporte incorporado para matrices, use listas. Definir una función, búsqueda binaria(), que acepta tres parámetros, la lista, su tamaño y un número a buscar:

definitivamentebúsqueda binaria(arr, arr_size, search_number):
 bajo = 0
 alto = arr_size - 1
mientras bajo <= alto:
 medio = bajo + (alto-bajo)//2
 if arr[mid] == número_búsqueda:
devolver medio
elif arr[mid] > buscar_número:
 alto = medio - 1
demás:
 bajo = medio + 1
devolver-1

Inicializar dos variables, bajo y alto, para que sirva como límite inferior y superior de la lista. Similar a la implementación de C, use un mientras bucle que reduce el espacio de búsqueda. Inicializar medio para almacenar el valor medio de la lista. Python proporciona el operador de división de piso (//) que proporciona el entero más grande posible.

Haga las comparaciones y reduzca el espacio de búsqueda hasta que el valor medio sea igual al número de búsqueda. Si el número de búsqueda no está presente, el control volverá -1.

arr_size = int (entrada ("Introduzca el número de elementos: "))
arr=[]
imprimir("Por favor ingrese números: ", fin="")
para i en rango (0,arr_size):
 arr.append(En t(aporte()))
numero_buscado = int (entrada("Introduzca el número a buscar: "))
resultado = búsqueda binaria (arr, arr_size, search_number)
si resultado == -1:
 imprimir("Número no presente")
demás:
 imprimir("Número es presente en la posición ", (resultado + 1))

Pruebe la función con la entrada del usuario. Usar aporte() para obtener el tamaño de la lista, su contenido y un número para buscar. Usar En t() para encasillar la entrada de cadena aceptada por Python como predeterminada en un número entero. Para agregar números a la lista, use el adjuntar() función.

Llamar búsqueda binaria() y pasar los argumentos. Si encuentra el número, muestre su posición o índice; de ​​lo contrario, aparecerá un mensaje que indica que el número no está presente.

Salida del algoritmo de búsqueda binaria

El siguiente es el resultado del algoritmo de búsqueda binaria cuando el elemento está presente en la matriz:

El siguiente es el resultado del algoritmo de búsqueda binaria cuando el elemento no está presente en la matriz:

Aprenda las estructuras de datos y algoritmos fundamentales

La búsqueda es uno de los primeros algoritmos que aprende y, a menudo, se le pregunta en concursos de codificación, ubicaciones y entrevistas. Algunos otros algoritmos que debe aprender son los algoritmos de clasificación, hashing, programación dinámica, coincidencia de cadenas y prueba de primalidad.

Además, es esencial comprender la complejidad temporal y espacial de los algoritmos. Son uno de los conceptos más cruciales en informática para determinar la eficiencia de cualquier algoritmo. Con conocimiento de estructuras de datos y algoritmos, está obligado a crear los mejores programas.