logo

TechCodeview

Algoritmo de búsqueda binaria: implementación iterativa y recursiva

Búsqueda binaria Algoritmo es un algoritmo de búsqueda utilizado en una matriz ordenada por dividir repetidamente el intervalo de búsqueda por la mitad . La idea de la búsqueda binaria es utilizar la información que está ordenada la matriz y reducir la complejidad del tiempo a O (log N).

Búsqueda binaria es un algoritmo de búsqueda utilizado para encontrar la posición de un valor objetivo dentro de un ordenado formación. Funciona dividiendo repetidamente el intervalo de búsqueda por la mitad hasta que se encuentra el valor objetivo o el intervalo está vacío. El intervalo de búsqueda se reduce a la mitad comparando el elemento objetivo con el valor medio del espacio de búsqueda.

actualizar desde unirse a sql

Para aplicar el algoritmo de búsqueda binaria:



  • La estructura de datos debe estar ordenada.
  • El acceso a cualquier elemento de la estructura de datos requiere un tiempo constante.

Algoritmo de búsqueda binaria:

En este algoritmo,

  • Divida el espacio de búsqueda en dos mitades por encontrar el índice medio .

Encontrar el índice medio en el algoritmo de búsqueda binaria

  • Compare el elemento central del espacio de búsqueda con la clave.
  • Si la clave se encuentra en el elemento medio, el proceso finaliza.
  • Si la clave no se encuentra en el elemento central, elija qué mitad se utilizará como el siguiente espacio de búsqueda.
    • Si la clave es más pequeña que el elemento del medio, entonces se utiliza el lado izquierdo para la siguiente búsqueda.
    • Si la clave es mayor que el elemento del medio, entonces se utiliza el lado derecho para la siguiente búsqueda.
  • Este proceso continúa hasta que se encuentra la clave o se agota el espacio total de búsqueda.

¿Cómo funciona el algoritmo de búsqueda binaria?

Para comprender el funcionamiento de la búsqueda binaria, considere la siguiente ilustración:

Considere una matriz arreglo[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , y el objetivo = 23 .

Primer paso: Calcule el medio y compare el elemento medio con la clave. Si la clave es menor que el elemento medio, muévase hacia la izquierda y si es mayor que el elemento medio, mueva el espacio de búsqueda hacia la derecha.

  • La clave (es decir, 23) es mayor que el elemento medio actual (es decir, 16). El espacio de búsqueda se mueve hacia la derecha.

Algoritmo de búsqueda binaria: comparar clave con 16

  • La clave es menor que la actual mid 56. El espacio de búsqueda se mueve hacia la izquierda.

Algoritmo de búsqueda binaria: comparar clave con 56

Segundo paso: Si la clave coincide con el valor del elemento intermedio, se encuentra el elemento y se detiene la búsqueda.

Algoritmo de búsqueda binaria: coincidencias de claves con mid

Práctica recomendada Búsqueda binaria ¡Pruébelo!

El Algoritmo de búsqueda binaria se puede implementar de las siguientes dos maneras

  • Algoritmo iterativo de búsqueda binaria
  • Algoritmo de búsqueda binaria recursiva

A continuación se muestran los pseudocódigos de los enfoques.

Algoritmo iterativo de búsqueda binaria:

Aquí usamos un bucle while para continuar el proceso de comparar la clave y dividir el espacio de búsqueda en dos mitades.

Implementación del algoritmo de búsqueda binaria iterativa:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
Java 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  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, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
Pitón 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
JavaScript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= bajo) { medio = bajo + Math.floor((alto - bajo) / 2);    // Si el elemento está presente en el medio // sí mismo if (arr[mid] == x) return mid;    // Si el elemento es más pequeño que mid, entonces // sólo puede estar presente en el subarreglo izquierdo si (arr[mid]> x) high = mid - 1;    // De lo contrario, el elemento solo puede estar presente // en el subarreglo derecho else low = mid + 1;  } // Llegamos aquí cuando el elemento // no está presente en la matriz return -1; } arr =nueva matriz(2, 3, 4, 10, 40);  x = 10;  n = longitud del arreglo;  resultado = búsqueda binaria (arr, x);   (resultado == -1)? console.log('El elemento no está presente en la matriz'): console.log ('El elemento está presente en el índice ' + resultado);   // Este código es aportado por simranarora5sos y rshuklabbb>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
Producción 
Element is present at index 3>

Complejidad del tiempo: O(logN)
Espacio Auxiliar: O(1)

Algoritmo de búsqueda binaria recursiva:

Cree una función recursiva y compare la mitad del espacio de búsqueda con la clave. Y según el resultado, devuelva el índice donde se encuentra la clave o llame a la función recursiva para el siguiente espacio de búsqueda.

Implementación del algoritmo de búsqueda binaria recursiva:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= bajo) { int mid = bajo + (alto - bajo) / 2;  // Si el elemento está presente en el medio // sí mismo if (arr[mid] == x) return mid;  // Si el elemento es más pequeño que mid, entonces // sólo puede estar presente en el subarreglo izquierdo si (arr[mid]> x) return binarioSearch(arr, low, mid - 1, x);  // De lo contrario, el elemento sólo puede estar presente // en el subarreglo derecho return binarioSearch(arr, mid + 1, high, x);  } } // Código del controlador int main() { int arr[] = { 2, 3, 4, 10, 40 };  consulta int = 10;  int n = tamaño de (arr) / tamaño de (arr [0]);  resultado int = búsqueda binaria (arr, 0, n - 1, consulta);  (resultado == -1)? corte<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= bajo) { int mid = bajo + (alto - bajo) / 2;  // Si el elemento está presente en el medio // sí mismo if (arr[mid] == x) return mid;  // Si el elemento es más pequeño que mid, entonces // sólo puede estar presente en el subarreglo izquierdo si (arr[mid]> x) return binarioSearch(arr, low, mid - 1, x);  // De lo contrario, el elemento sólo puede estar presente // en el subarreglo derecho return binarioSearch(arr, mid + 1, high, x);  } // Llegamos aquí cuando el elemento // no está presente en la matriz return -1; } // Código del controlador int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = tamaño de (arr) / tamaño de (arr [0]);  entero x = 10;  resultado int = búsqueda binaria (arr, 0, n - 1, x);  (resultado == -1)? printf('El elemento no está presente en la matriz'): printf('El elemento está presente en el índice %d', resultado);  devolver 0; }>
Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= bajo) { int mid = bajo + (alto - bajo) / 2;  // Si el elemento está presente en el // medio mismo if (arr[mid] == x) return mid;  // Si el elemento es más pequeño que mid, entonces // sólo puede estar presente en el subarreglo izquierdo si (arr[mid]> x) return binarioSearch(arr, low, mid - 1, x);  // De lo contrario, el elemento sólo puede estar presente // en el subarreglo derecho return binarioSearch(arr, mid + 1, high, x);  } // Llegamos aquí cuando el elemento no está presente // en la matriz return -1;  } // Código del controlador public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arreglo[] = { 2, 3, 4, 10, 40 };  int n = longitud del arreglo;  entero x = 10;  resultado int = ob.binarySearch(arr, 0, n - 1, x);  if (resultado == -1) System.out.println( 'El elemento no está presente en la matriz');  else System.out.println( 'Elemento está presente en el índice ' + resultado);  } } /* Este código es una contribución de Rajat Mishra */>
Pitón 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= bajo: medio = bajo + (alto - bajo) // 2 # Si el elemento está presente en el medio if arr[mid] == x: return mid # Si el elemento es más pequeño que mid, entonces # solo puede estar presente en el subarreglo izquierdo elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # De lo contrario, el elemento solo puede estar presente # en el subarreglo derecho else: return binarioSearch(arr, mid + 1, high, x ) # El elemento no está presente en la matriz else: return -1 # Código del controlador if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Resultado de la llamada a la función = binarioSearch( arr, 0, len(arr)-1, x) si resultado!= -1: print('El elemento está presente en el índice', resultado) else: print('Elemento no está presente en la matriz')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= bajo) { int mid = bajo + (alto - bajo) / 2;  // Si el elemento está presente en el // medio mismo if (arr[mid] == x) return mid;  // Si el elemento es más pequeño que mid, entonces // sólo puede estar presente en el subarreglo izquierdo si (arr[mid]> x) return binarioSearch(arr, low, mid - 1, x);  // De lo contrario, el elemento sólo puede estar presente // en el subarreglo derecho return binarioSearch(arr, mid + 1, high, x);  } // Llegamos aquí cuando el elemento no está presente // en la matriz return -1;  } // Código del controlador public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = longitud de arreglo;  entero x = 10;  resultado int = búsqueda binaria (arr, 0, n - 1, x);  if (resultado == -1) Console.WriteLine( 'Elemento no está presente en arrau');  else Console.WriteLine('Elemento está presente en el índice ' + resultado);  } } // Este código es aportado por Sam007.>
JavaScript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= bajo) { let mid = bajo + Math.floor((alto - bajo) / 2);  // Si el elemento está presente en el medio // sí mismo if (arr[mid] == x) return mid;  // Si el elemento es más pequeño que mid, entonces // sólo puede estar presente en el subarreglo izquierdo si (arr[mid]> x) return binarioSearch(arr, low, mid - 1, x);  // De lo contrario, el elemento sólo puede estar presente // en el subarreglo derecho return binarioSearch(arr, mid + 1, high, x);  } // Llegamos aquí cuando el elemento // no está presente en la matriz return -1; } let arr = [ 2, 3, 4, 10, 40 ]; sea ​​x = 10; let n = arr.length let resultado = binarioSearch(arr, 0, n - 1, x); (resultado == -1)? console.log('El elemento no está presente en la matriz'): console.log('El elemento está presente en el índice ' +resultado);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $bajo) { $medio = techo($bajo + ($alto - $bajo) / 2); // Si el elemento está presente // en el medio mismo if ($arr[$mid] == $x) return floor($mid); // Si el elemento es menor que // mid, entonces sólo puede // estar presente en el subarreglo izquierdo si ($arr[$mid]> $x) return binarioSearch($arr, $low, $mid - 1, $x ); // De lo contrario, el elemento sólo // puede estar presente en el subarreglo derecho return binarioSearch($arr, $mid + 1, $high, $x); } // Llegamos aquí cuando el elemento // no está presente en la matriz return -1; } // Código del controlador $arr = array(2, 3, 4, 10, 40); $n = contar($arr); $x = 10; $resultado = búsqueda binaria($arr, 0, $n - 1, $x); if(($resultado == -1)) echo 'El elemento no está presente en la matriz'; else echo 'El elemento está presente en el índice ', $resultado; ?>>
Producción 
Element is present at index 3>
  • Complejidad del tiempo:
    • Mejor caso: O(1)
    • Caso promedio: O (log N)
    • Peor caso: O(log N)
  • Espacio Auxiliar: O (1). Si se considera la pila de llamadas recursiva, el espacio auxiliar será O (logN).
  • La búsqueda binaria se puede utilizar como elemento básico para algoritmos más complejos utilizados en el aprendizaje automático, como algoritmos para entrenar redes neuronales o encontrar los hiperparámetros óptimos para un modelo.
  • Se puede utilizar para buscar en gráficos por computadora, como algoritmos de trazado de rayos o mapeo de texturas.
  • Se puede utilizar para buscar en una base de datos.
  • La búsqueda binaria es más rápida que la búsqueda lineal, especialmente para matrices grandes.
  • Más eficiente que otros algoritmos de búsqueda con una complejidad temporal similar, como la búsqueda por interpolación o la búsqueda exponencial.
  • La búsqueda binaria es adecuada para buscar grandes conjuntos de datos almacenados en una memoria externa, como en un disco duro o en la nube.
  • La matriz debe estar ordenada.
  • La búsqueda binaria requiere que la estructura de datos que se busca se almacene en ubicaciones de memoria contiguas.
  • La búsqueda binaria requiere que los elementos de la matriz sean comparables, lo que significa que deben poder ordenarse.

Preguntas frecuentes (FAQ) sobre la búsqueda binaria:

1. ¿Qué es la búsqueda binaria?

La búsqueda binaria es un algoritmo eficaz para encontrar un valor objetivo dentro de una matriz ordenada. Funciona dividiendo repetidamente el intervalo de búsqueda por la mitad.

2. ¿Cómo funciona la búsqueda binaria?

La búsqueda binaria compara el valor objetivo con el elemento central de la matriz. Si son iguales, la búsqueda es exitosa. Si el objetivo es menor que el elemento del medio, la búsqueda continúa en la mitad inferior de la matriz. Si el objetivo es mayor, la búsqueda continúa en la mitad superior. Este proceso se repite hasta que se encuentra el objetivo o el intervalo de búsqueda está vacío.

3. ¿Cuál es la complejidad temporal de la búsqueda binaria?

La complejidad temporal de la búsqueda binaria es O (log2n), donde n es el número de elementos de la matriz. Esto se debe a que el tamaño del intervalo de búsqueda se reduce a la mitad en cada paso.

4. ¿Cuáles son los requisitos previos para la búsqueda binaria?

La búsqueda binaria requiere que la matriz esté ordenada en orden ascendente o descendente. Si la matriz no está ordenada, no podemos usar la búsqueda binaria para buscar un elemento en la matriz.

5. ¿Qué sucede si la matriz no está ordenada para la búsqueda binaria?

Si la matriz no está ordenada, la búsqueda binaria puede arrojar resultados incorrectos. Se basa en la naturaleza ordenada de la matriz para tomar decisiones sobre en qué mitad de la matriz buscar.

6. ¿Se puede aplicar la búsqueda binaria a datos no numéricos?

Sí, la búsqueda binaria se puede aplicar a datos no numéricos siempre que exista un orden definido para los elementos. Por ejemplo, se puede utilizar para buscar cadenas en orden alfabético.

7. ¿Cuáles son algunas desventajas comunes de la búsqueda binaria?

La desventaja de la búsqueda binaria es que es necesario ordenar la matriz de entrada para decidir en qué mitad puede encontrarse el elemento de destino. Por lo tanto, para matrices no ordenadas, debemos ordenar la matriz antes de aplicar la búsqueda binaria.

8. ¿Cuándo se debe utilizar la búsqueda binaria?

La búsqueda binaria debe usarse cuando se busca un valor objetivo en una matriz ordenada, especialmente cuando el tamaño de la matriz es grande. Es particularmente eficiente para conjuntos de datos grandes en comparación con los algoritmos de búsqueda lineal.

9. ¿Se puede implementar la búsqueda binaria de forma recursiva?

Sí, la búsqueda binaria se puede implementar de forma iterativa y recursiva. La implementación recursiva a menudo conduce a un código más conciso, pero puede tener una sobrecarga ligeramente mayor debido al espacio de pila recursivo o a las llamadas a funciones.

10. ¿La búsqueda binaria es siempre la mejor opción para buscar en una matriz ordenada?

Si bien la búsqueda binaria es muy eficiente para buscar en matrices ordenadas, puede haber casos específicos en los que otros algoritmos de búsqueda sean más apropiados, como cuando se trata de conjuntos de datos pequeños o cuando la matriz se modifica con frecuencia.

ordenar burbujas en java

Artículos relacionados:

  • Tutorial de búsqueda binaria en respuesta con problemas
  • Búsqueda lineal versus búsqueda binaria
  • ¿Cómo identificar y resolver problemas de búsqueda binaria?