Saltar al contenido

Cómo implementar la búsqueda binaria usando el método iterativo

Uno de los algoritmos más fundamentales en informática es el algoritmo de búsqueda binaria. Puede implementar la búsqueda binaria de dos formas: 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 (regístrate) 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?


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

Si el elemento de búsqueda es más grande que el elemento del medio, significa que todos los elementos de la izquierda 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.

Del mismo modo, si el elemento de búsqueda es más pequeño que el elemento del medio, significa que todos los elementos de la derecha 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 la cantidad de comparaciones en comparación con la implementación de búsqueda lineal, donde la cantidad de comparaciones es igual a la cantidad de elementos en el peor de los casos. Este método es muy útil para encontrar números en una guía telefónica o palabras en un diccionario.

Aquí hay una representación esquemática del algoritmo de búsqueda binaria:

Búsqueda binaria con C

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

El código fuente completo del programa de búsqueda binaria con C, C++, Java y Python se encuentra aquí repositorio GitHub.

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

#include <stdio.h>
int binarySearch(int arr[], int arr_size, int search_number) {
}

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 otra manera no tendría sentido. Puede pedirle al usuario una matriz ordenada o usar algoritmos de clasificación como Bubble o Selection sort.

los 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:

    int low = 0, high = arr_size - 1, mid;

el más importante tiempo() loop reducirá el espacio de búsqueda. Si el valor del índice bajo alguna vez excede el índice alto, entonces el espacio de búsqueda se agota y el valor no puede estar presente.

    while (low <= high) {
}
return -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 valor que estamos buscando, devuelva ese índice.
  2. Si el valor del punto medio es mayor que el valor que buscamos, baje el máximo.
  3. Si el valor del punto medio es más bajo, aumente el valor más bajo.

        
mid = (low + (high - low)) / 2;
if (arr[mid] == search_number)
return mid;
else if (arr[mid] > search_number)
high = mid - 1;
else
low = mid + 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:

int main() {
int arr[100], i, arr_size, search_number;
printf("Enter number of elements: ");
scanf("%d", &arr_size);
printf("Please enter numbers: ");
for (i = 0; i < arr_size; i++) {
scanf("%d", &arr[i]);
}
printf("Enter number to be searched: ");
scanf("%d", &search_number);
i = binarySearch(arr, arr_size, search_number);
if (i==-1)
printf("Number not present");
else
printf("Number is present at position %d", i + 1);
return 0;
}

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

Búsqueda binaria con C++

Puede convertir el programa C a un programa C++ usando el Corriente de salida de entrada y usar espacio de nombres estándar para evitar repetirlo varias veces en el programa.

#include <iostream>
using namespace std;

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

printf("Enter number of elements: ");
cout << "Enter number of elements: ";
scanf("%d", &arr_size);
cin >> arr_size;

Búsqueda binaria con Python

Dado que Python no tiene soporte integrado para matrices, usa listas. Definir una función, Búsqueda binaria()que acepta tres parámetros, la lista, el tamaño y un número a buscar:

def binarySearch(arr, arr_size, search_number):
low = 0
high = arr_size - 1
while low <= high:
mid = low + (high-low)
if arr[mid] == search_number:
return mid
elif arr[mid] > search_number:
high = mid - 1
else:
low = mid + 1
return -1

Inicializar dos variables, bajo y alto, para servir como los límites superior e inferior de la lista. Al igual que con la implementación de C, utilice un tiempo 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 devuelve 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 devuelve -1.

arr_size = int(input("Enter number of elements: "))
arr=[]
print("Please enter numbers: ", end=" ")
for i in range(0,arr_size):
arr.append(int(input()))
search_number = int(input("Enter number to be searched: "))
result = binarySearch(arr, arr_size, search_number)
if result == -1:
print("Number not present")
else:
print("Number is present at position ", (result + 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 escribir la entrada de cadena aceptada como predeterminada por Python en un número entero. Use el para agregar canciones a la lista agregar () función.

Llamada telefónica Búsqueda binaria() y pasar los argumentos. Si encuentra el número, muestre la posición o el índice; de ​​lo contrario, un mensaje de 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 solicita 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 números primos.

Además, es fundamental 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 el conocimiento de estructuras de datos y algoritmos, tiene la garantía de crear los mejores programas.