Ni siquiera un pase de un solo día, cuando no tenemos que buscar algo en nuestro día a día, llaves de automóvil, libros, bolígrafo, cargador de móvil y lo que no. Lo mismo es la vida de una computadora, hay tantos datos almacenados en ella, que cada vez que un usuario pide algunos datos, la computadora tiene que buscar en su memoria para buscar los datos y ponerlos a disposición del usuario. Y la computadora tiene sus propias técnicas para buscar en su memoria rápidamente, sobre las que puede obtener más información en nuestra serie de tutoriales sobre el sistema operativo.
¿Qué pasa si tienes que escribir un programa para buscar un número determinado en una matriz? ¿Cómo lo harás?
Bueno, para buscar un elemento en una matriz dada, hay dos algoritmos populares disponibles:
- Búsqueda lineal
- Búsqueda binaria
Búsqueda lineal
La búsqueda lineal es un algoritmo de búsqueda muy básico y simple. En la búsqueda lineal, buscamos un elemento o valor en un array dado recorriendo el array desde el principio, hasta que se encuentra el elemento o valor deseado.
Compara el elemento a buscar con todos los elementos presentes en el array y cuando el elemento se compara con éxito, devuelve el índice del elemento en el array, de lo contrario devuelve -1.
La búsqueda lineal se aplica en listas sin clasificar o desordenadas, cuando hay menos elementos en una lista.
Características del algoritmo de búsqueda lineal
- Se utiliza para una pequeña lista de elementos sin clasificar y sin ordenar.
- Tiene una complejidad de tiempo de O (n), lo que significa que el tiempo depende linealmente del número de elementos, lo que no es malo, pero tampoco tan bueno.
- Tiene una implementación muy simple.
Implementaremos el algoritmo de búsqueda Lineal en el siguiente tutorial.
Búsqueda binaria
La búsqueda binaria se utiliza con una matriz o lista ordenada. En la búsqueda binaria, seguimos los siguientes pasos:
- comenzamos comparando el elemento buscado con el elemento en el medio de la lista o matriz.
- Si obtenemos una coincidencia, devolvemos el índice del elemento central.
- Si no obtenemos una coincidencia, verificamos si el elemento a buscar es menor o mayor que el valor del elemento central.
- Si el elemento / número a buscar es mayor en valor que el número del medio, entonces elegimos los elementos en el lado derecho del elemento del medio(como la lista/matriz está ordenada, por lo tanto, a la derecha, tendremos todos los números mayores que el número del medio), y comenzamos de nuevo desde el paso 1.
- Si el elemento / número a buscar tiene un valor menor que el número del medio, elegimos los elementos del lado izquierdo del elemento del medio y comenzamos de nuevo desde el paso 1.
La búsqueda binaria es útil cuando hay un gran número de elementos en una matriz y están ordenados.
Así que una condición necesaria para que la búsqueda binaria funcione es que la lista / matriz esté ordenada.
Características de Búsqueda binaria
- Es genial buscar a través de matrices ordenadas grandes.
- Tiene una complejidad de tiempo de O (log n), que es una complejidad de tiempo muy buena. Discutiremos esto en detalle en el tutorial de búsqueda binaria.
- Tiene una implementación simple.