Búsqueda lineal vs búsqueda binaria: diferencia entre búsqueda lineal y búsqueda binaria

Publicado: 2021-02-09

Tabla de contenido

Introducción

La asignación de memoria contigua en lenguajes de programación proporciona una implementación flexible para almacenar múltiples puntos de datos. Esto se puede utilizar en su punto máximo si queremos segregar los datos y fusionar todos los datos similares en una estructura de datos contigua como una matriz, lista, etc.

La asignación de memoria contigua tiene muchas implementaciones en aplicaciones del mundo real, como un sistema operativo en computadoras, sistemas de administración de bases de datos, etc. Esta estructura de datos se considera flexible porque agregar un nuevo punto de datos a una matriz solo requiere una sola unidad de tiempo, es decir; O(1).

Pero el problema surge cuando queremos ver una entrada en particular o buscar una entrada en particular porque todas las aplicaciones del mundo real dependen de los comandos de acceso a datos. Y esta tarea debe ser lo suficientemente rápida para cumplir con la velocidad del procesador y la memoria.

Hay varios algoritmos de búsqueda divididos en función del número de comparaciones que hacemos para buscar el elemento.

Si comparamos cada punto de datos en la matriz para buscar un elemento, entonces se considera una búsqueda secuencial. Pero si estamos comparando solo unos pocos elementos omitiendo algunas de las comparaciones, entonces se considera una búsqueda de intervalo. Pero necesitamos que una matriz esté en orden (orden ascendente o descendente) para realizar una búsqueda de intervalo en ella.

La complejidad temporal de la búsqueda secuencial es O(n) lineal, y la complejidad temporal de la búsqueda binaria (un ejemplo de búsqueda por intervalos) es O(log n). Además, existen otros algoritmos de búsqueda como la búsqueda exponencial, la búsqueda por salto, etc.

Pero la búsqueda lineal y la búsqueda binaria se usan principalmente, donde la búsqueda lineal es para datos aleatorios o no ordenados y la búsqueda binaria es para datos ordenados y ordenados. Hashing es un algoritmo de búsqueda especial en el que la complejidad temporal de acceder a un punto de datos es O(1).

Primero analicemos los algoritmos de búsqueda lineal y búsqueda binaria y luego comparemos las diferencias entre la búsqueda lineal y la búsqueda binaria.

Búsqueda lineal

Como ya se discutió, el algoritmo de búsqueda lineal compara cada elemento en la matriz, y aquí está el código para hacerlo.

clase pública UpGrad {
 public static int linear_search ( int [] arr, int n, int k){
 para ( int i= 0 ; i<n; i++)
 si (arr[i]==k)
 devuelve i+ 1 ;
 retorno – 1 ;
 }
 public static void principal (String[] args){
 int [] arr= new int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 int k= 13 ;
 int n=arr.longitud;
 int r=búsqueda_lineal(arr, n, k);
 si (r==- 1 )
 System.out.println( “elemento no encontrado” );
 demás
 System.out.println( “elemento encontrado en la posición “ +r+ ”” );
 }
 }

Repasemos el código.

Hemos declarado una función de búsqueda_lineal, que espera una matriz, clave entera como parámetros. Ahora necesitamos recorrer todos los elementos y comparar si coincide con nuestra clave de búsqueda, por lo que hemos escrito un ciclo for que recorre la matriz y, dentro de él, hay un ciclo if que verifica si el número en esa posición coincide con la clave de búsqueda o no. Si encontramos una coincidencia, devolveremos la posición. Si no existe tal elemento en la matriz, devolveremos -1 al final de la función.

Tenga en cuenta que si tenemos varias apariciones del mismo número, devolveremos la posición de su primera aparición.

Llegando al método principal, hemos declarado e inicializado una matriz de enteros. Luego estamos inicializando la clave que debe buscarse. Aquí estamos codificando la matriz y la clave, pero puede cambiarla a la entrada del usuario. Ahora que tenemos la lista de elementos y la clave para buscar, se llama al método de búsqueda lineal y se anota el índice devuelto. Más tarde, verificamos el valor devuelto e imprimimos el índice si existe la clave; de ​​lo contrario, no se encuentra la clave de impresión.

Búsqueda binaria

La búsqueda binaria está más optimizada que la búsqueda lineal, pero la matriz debe ordenarse para aplicar la búsqueda binaria. Y aquí está el código para hacer eso.

clase pública UpGrad {
 public static int binary_search ( int [] arr, int k){
 int l= 0 ,h=arr.length- 1 ,mid= 0 ;
 mientras (l<=h){
 medio=l+(hl)/ 2 ;
 si (arr[medio]==k)
 volver medio+ 1 ;
 si no ( arr [mid]>k)
 h=media- 1 ;
 demás
 l=medio+ 1 ;
 }
 retorno – 1 ;
 }
 public static void principal (String[] args){
 int [] arr= new int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 int k= 8 ;
 int r=búsqueda_binaria(arr,k);
 si (r==- 1 )
 System.out.println( “elemento no encontrado” );
 demás
 System.out.println( “elemento encontrado en la posición “ +r+ ”” );
 }
 }

Repasemos el código.

Hemos declarado un método binary_search que espera una matriz de enteros ordenados y una clave de enteros como parámetros. Estamos inicializando las variables bajo, alto, medio. Aquí low, high son punteros donde low estará en el índice 0 y high estará en el índice n al principio. Entonces, ¿cómo funciona la búsqueda binaria?

Al principio, calcularemos el medio de bajo y alto. Podemos calcular el medio como (bajo+alto)/2, pero a veces alto puede ser un número grande, y sumar bajo al alto puede provocar un desbordamiento de enteros. Entonces, calcular el medio como bajo+(alto-bajo)/2 sería una forma óptima.

Compararemos el elemento en el medio con la clave de búsqueda y devolveremos el índice si encontramos una coincidencia. De lo contrario, comprobaremos si el elemento medio es mayor que la tecla o más pequeño que la tecla. Si el valor medio es mayor, debemos verificar solo la primera mitad de la matriz porque todos los elementos en la segunda mitad de la matriz son mayores que la clave, por lo que actualizaremos el valor alto a la mitad de 1.

De manera similar, si mid es menor que key, entonces necesitamos buscar en la segunda mitad de la matriz, por lo tanto, actualizamos low to mid+1. Recuerde que la búsqueda binaria se basa en el algoritmo de disminución y conquista ya que estamos ignorando una de las mitades de la matriz en cada iteración.

Volviendo a nuestro código, hemos construido el método principal. Inicializó una matriz ordenada y una clave de búsqueda, realizó una llamada a la búsqueda binaria e imprimió los resultados.

Ahora que hemos recorrido los algoritmos de búsqueda lineal y búsqueda binaria, comparemos ambos algoritmos.

Búsqueda lineal vs búsqueda binaria

Trabajando

  • La búsqueda lineal itera a través de todos los elementos y los compara con la clave que se debe buscar.
  • La búsqueda binaria disminuye sabiamente el tamaño de la matriz que debe buscarse y compara la clave con el elemento medio cada vez.

Estructura de datos

  • La búsqueda lineal es flexible con todas las estructuras de datos como una matriz, una lista, una lista vinculada, etc.
  • La búsqueda binaria no se puede realizar en todas las estructuras de datos, ya que necesitamos un recorrido multidireccional. Por lo tanto, no se pueden utilizar estructuras de datos como la lista enlazada única.

requisitos previos

  • La búsqueda lineal se puede realizar en todo tipo de datos, los datos pueden ser aleatorios u ordenados, el algoritmo sigue siendo el mismo. Por lo tanto, no es necesario realizar ningún trabajo previo.
  • La búsqueda binaria solo funciona en una matriz ordenada. Por lo tanto, ordenar una matriz es un requisito previo para este algoritmo.

Caso de uso

  • Por lo general, se prefiere la búsqueda lineal para conjuntos de datos más pequeños y ordenados aleatoriamente.
  • Se prefiere la búsqueda binaria para conjuntos de datos comparativamente más grandes y ordenados.

Eficacia

  • La búsqueda lineal es menos eficiente en el caso de conjuntos de datos más grandes.
  • La búsqueda binaria es más eficiente en el caso de conjuntos de datos más grandes.

Complejidad del tiempo

  • En la búsqueda lineal, la complejidad del mejor de los casos es O(1) donde el elemento se encuentra en el primer índice. La complejidad del peor de los casos es O(n) donde el elemento se encuentra en el último índice o el elemento no está presente en la matriz.
  • En la búsqueda binaria, la complejidad del mejor de los casos es O(1) donde el elemento se encuentra en el índice medio. La complejidad del peor de los casos es O( log 2 n).

Ejecución en seco

Supongamos que tenemos una matriz de tamaño 10.000.

  • En una búsqueda lineal, la complejidad del mejor de los casos es O(1) y la complejidad del peor de los casos es O(10000).
  • En una búsqueda binaria, la complejidad del mejor de los casos es O(1) y la complejidad del peor de los casos es O( log 2 10000)=O(13.287).

Conclusión

Hemos entendido la importancia de acceder a los datos en matrices, hemos entendido los algoritmos de la búsqueda lineal y la búsqueda binaria. Recorrido los códigos de búsqueda lineal y búsqueda binaria. Comparó las diferencias entre la búsqueda lineal y la búsqueda binaria, hizo un ensayo para un ejemplo de gran tamaño.

Ahora que conoce las diferencias entre la búsqueda lineal y la búsqueda binaria, intente ejecutar ambos códigos para un conjunto de datos de gran tamaño y compare el tiempo de ejecución, comience a explorar diferentes algoritmos de búsqueda e intente implementarlos.

Si tiene curiosidad por aprender sobre ciencia de datos, consulte el Diploma PG en ciencia de datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos, tutoría con expertos de la industria, 1- on-1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.

Aprenda cursos de ciencia de datos en línea de las mejores universidades del mundo. Obtenga programas Executive PG, programas de certificados avanzados o programas de maestría para acelerar su carrera.

Compare la búsqueda lineal y la búsqueda binaria usando sus complejidades.

La búsqueda binaria es más optimizada y eficiente que la búsqueda lineal en muchos aspectos, especialmente cuando los elementos están ordenados. La razón se reduce a las complejidades de ambas búsquedas.
Búsqueda lineal
1. Complejidad de tiempo: O(N) - Dado que en la búsqueda lineal, recorremos la matriz para verificar si algún elemento coincide con la clave. En el peor de los casos, el elemento estará presente al final de la matriz, por lo que tenemos que atravesar hasta el final y, por lo tanto, la complejidad del tiempo será O (N), donde N es el número total de elementos de la matriz.
2. Complejidad del espacio: O(1) - No estamos utilizando ningún espacio adicional, por lo que la complejidad del espacio será O(1).
Búsqueda binaria
1. Complejidad de tiempo: O (log N) : en la búsqueda binaria, la búsqueda se reduce a la mitad, ya que solo tenemos que buscar en la mitad de la matriz. Y estamos constantemente acortando nuestra búsqueda a la mitad de la sección donde está presente el elemento.
2. Complejidad espacial: O(1)
- No estamos utilizando ningún espacio extra por lo que la complejidad del espacio será O(1).

¿Hay algún otro método para buscar un elemento en una matriz?

Aunque la búsqueda lineal y la búsqueda binaria se utilizan a menudo para realizar búsquedas, existe otro método de búsqueda: el método de interpolación. Es una versión optimizada de Binary Search donde todos los elementos se distribuyen uniformemente.
La idea detrás de este método es que en la búsqueda binaria, siempre buscamos en el centro de la matriz. Pero en este método, la búsqueda puede ir a diferentes lugares dependiendo de dónde se encuentre la clave. Por ejemplo, si la clave se encuentra cerca del último elemento de la matriz, la búsqueda comenzará desde el final de la matriz.

¿Cuáles son las diferentes complejidades temporales de la búsqueda por interpolación?

En el peor de los casos, la complejidad temporal de la búsqueda por interpolación es O(N) ya que, en el peor de los casos, la clave estará al final de la matriz, por lo que el iterador tiene que recorrer toda la matriz.
La complejidad promedio del caso será O(log(log N) ya que el elemento puede estar en cualquier parte de la matriz. También puede estar cerca del punto de inicio.
La complejidad del mejor de los casos será O(1) ya que, en el mejor de los casos, la clave será el primer elemento de la matriz.