La búsqueda se puede hacer en estructuras de datos internas o en estructuras de datos externas. La recuperación de información en el formato requerido es la actividad central en todas las aplicaciones informáticas. Esto implica buscar. Este bloque trata sobre técnicas de búsqueda. Los métodos de búsqueda están diseñados para aprovechar la organización de archivos y optimizar la búsqueda de un registro en particular o para establecer su ausencia. La organización de archivos y el método de búsqueda elegido pueden marcar una diferencia sustancial en el rendimiento de una aplicación.
Para buscar un elemento en una matriz dada, se puede hacer de las siguientes maneras:
1. Búsqueda lineal
- Cómo aprender algoritmos de manera fácil
- Estoy tratando de incrementar un elemento de matriz de caracteres inicializado a cero pero no puedo, ¿por qué?
- ¿Cuál sería un algoritmo para aplicar un filtro rosa a una imagen?
- ¿El aprendizaje por refuerzo está recibiendo actualmente más atención que los algoritmos genéticos?
- Si descubrieras un algoritmo simple que encuentra solo y todos los primos, ¿para qué podría usarse? ¿Es esto posible?
Comience al principio de la lista y verifique cada elemento de la lista. Muy lento [orden O (n)] pero funciona en una lista sin ordenar.
Algoritmo de búsqueda lineal
Esto representa el algoritmo para buscar una lista de valores para encontrar el requerido.
ENTRADA: Lista de tamaño N. Valor objetivo T
SALIDA: Posición de T en la lista I
EMPEZAR
1. Establezca ENCONTRADO en falso
Establecer I a 0
2. Mientras (I <= N) y (ENCONTRADO es falso)
Si la lista [I] = T
ENCONTRADO = verdadero
Más
I = I + 1
FIN
3. Si ENCONTRADO es falso
T no está presente en la lista.
FIN
Análisis de búsqueda lineal
Ya sea que la búsqueda secuencial se lleve a cabo en listas implementadas como matrices o listas vinculadas o en archivos, la parte fundamental del rendimiento es el paso 2 del bucle de comparación. Obviamente, cuanto menor sea el número de comparaciones, antes terminará el algoritmo.
La menor cantidad posible de comparaciones = 1. Cuando el elemento requerido es el primer elemento de la lista. Las comparaciones máximas = N cuando el elemento requerido es el último elemento de la lista. Por lo tanto, si el elemento requerido está en la posición I en la lista, se requieren comparaciones. Por lo tanto, el número promedio de comparaciones realizadas por búsqueda secuencial es (N + 1) / 2
La búsqueda secuencial es fácil de escribir y eficiente para listas cortas. No requiere datos ordenados. Sin embargo, es desastroso para largas listas. No hay forma de establecer rápidamente que el elemento requerido no está en la lista o de encontrar todas las ocurrencias de un elemento requerido en un solo lugar. Podemos superar estas deficiencias con la búsqueda binaria.
Ejemplo 1. Programa para buscar un artículo usando la búsqueda lineal.
#include
/ * Buscar clave en la lista * /
int seq_search (clave int, int a [], int n)
{
Int I;
para (i = 0; i <n; i ++)
{
Si (una tecla [i] ==) devuelve i + 1
}
devuelve 0;
}
vacío principal()
{
int I, n, clave, pos, a [20];
printf (“Ingrese el valor de n”);
scanf (“% d”, & n);
printf (“Ingrese n valoresn”);
para (i = 0; i <n; i ++)
scanf (“% d”, y a [i]);
printf (“Ingrese el elemento a buscar”);
scanf (“% d”, & clave);
pos = seq_search (clave, n, a);
si (pos == 0)
printf (“Búsqueda n incorrecta”);
más
printf (“clave encontrada en la posición =% d n”, pos);
}
Ejemplo 2 . con implementación
Para buscar el elemento 5, irá paso a paso en un orden de secuencia.
función findIndex (valores, objetivo)
{
para (var i = 0; i <valores.length; ++ i)
{
if (valores [i] == objetivo)
{
volver i;
}
}
volver -1;
}
// llama a la función findIndex con matriz y número a buscar
findIndex ([8, 2, 6, 3, 5], 5);
2. Búsqueda binaria
Esto se utiliza para buscar en una matriz ordenada. Prueba el elemento del medio de la matriz. Si es muy grande Repita el proceso en la mitad izquierda de la matriz y la mitad derecha si es demasiado pequeño. De esta manera, la cantidad de espacio que debe buscarse se reduce a la mitad cada vez, por lo que el tiempo es O (log n).
Ejemplo 1. Busque la página número 6 en un libro de 20 páginas
Un ejemplo típico de búsqueda binaria es buscar una página en un libro. Supongamos que estaba buscando la página 6 en el libro de 20 páginas. Primero lo abrirías al azar hacia la mitad posterior del libro. Si la página es menor que 6, se abriría en una página a la derecha, es mayor que 6 que se abriría en una página a la izquierda, repitiendo el proceso hasta que se encuentre la página 6. Como puede ver, en la primera búsqueda instintiva, redujo drásticamente el número de páginas para buscar.
En el ejemplo anterior, tenemos una lista ordenada de tamaño 20. La primera comparación es con el elemento medio Página número 10. Esto elimina los últimos 10 elementos, ya que la página 6 es menor que 10. La segunda comparación es con el elemento medio de Página 1 a página 10, es decir, con la página 5. Esto elimina la página 1 a la página 5, ya que la página 6 es mayor que la página 5. Esto continúa hasta que se encuentre la página 6. Ahora formulemos el algoritmo para la búsqueda binaria.
Algoritmo de Búsqueda Binaria
Esto representa el método de búsqueda binaria para encontrar un elemento requerido en una lista ordenada en orden creciente.
ENTRADA: LISTA ordenada de tamaño N, Valor objetivo T
SALIDA: Posición de T en la LISTA = I
EMPEZAR
1. MAX = N
MIN = 1
ENCONTRADO = falso
2. MIENTRAS (ENCONTRADO es falso) y (MAX> = MIN)
2.1 MID = (MAX + MIN) DIV 2
2.2 Si T = LISTA [MEDIO]
I = MEDIO
ENCONTRADO = verdadero
De lo contrario si T <LISTA [MEDIO]
MAX = MID-1
Más
MIN = MD + 1
FIN
Análisis de búsqueda binaria
El método de búsqueda binaria no necesita; más de [Iog2n] + 1 comparaciones. Esto implica que para una matriz de un millón de entradas, solo se necesitarán unas veinte comparaciones. Compare esto con el caso de búsqueda secuencial que en promedio necesitará (n + 1) / 2 comparaciones.
En el método de búsqueda binaria que se acaba de describir, siempre es la clave en el medio de la lista que se está examinando actualmente la que se utiliza para la comparación. La división de la lista se puede ilustrar a través de un árbol de decisión binario en el que el valor de un nodo es el índice de la clave que se está probando.
Supongamos que hay 31 registros, entonces la primera clave comparada está en la ubicación 16 de la lista ya que (1 + 31) / 2 = 16. Si la clave es menor que la clave en la ubicación 16, la ubicación 8 se prueba desde (1 + 15 ) / 2 = 8; o si la clave es menor que la clave en la ubicación 16, entonces la ubicación 24 se prueba.
Ejemplo-2. Programa para buscar un artículo usando la Búsqueda Binaria
#include
int main ()
{
int c, first, last, middle, n, search, array [100];
printf (“Ingrese el número de elementos \ n”);
scanf (“% d”, & n);
printf (“Ingrese% d enteros \ n”, n);
para (c = 0; c <n; c ++)
scanf (“% d”, & array [c]);
printf (“Ingrese el valor para encontrar \ n”);
scanf (“% d”, & búsqueda);
primero = 0;
último = n – 1;
medio = (primero + último) / 2;
while (primero <= último)
{
if (matriz [medio] <búsqueda)
primero = medio + 1;
si no (matriz [medio] == búsqueda)
{
printf (“% d encontrado en la ubicación% d. \ n”, búsqueda, medio + 1);
rotura;
}
más
último = medio – 1;
medio = (primero + último) / 2;
}
if (primero> último)
printf (“¡No encontrado!% d no está presente en la lista. \ n”, buscar);
devuelve 0;
}
Ejemplo-3. con implementación
Para buscar un elemento 13 de la matriz o lista ordenada.
función findIndex (valores, objetivo)
{
return binarySearch (valores, objetivo, 0, valores.length – 1);
};
función binarySearch (valores, objetivo, inicio, fin) {
if (inicio> fin) {return -1; } //no existe
var middle = Math.floor ((inicio + fin) / 2);
valor var = valores [medio];
if (value> target) {return binarySearch (valores, target, start, middle-1); }
if (value <target) {return binarySearch (valores, target, middle + 1, end); }
volver medio; //¡encontró!
}
findIndex ([2, 4, 7, 9, 13, 15], 13);
En la lógica del programa anterior, primero estamos comparando el número medio de la lista, con el objetivo, si coincide, devolvemos. Si no es así, vemos si el número del medio es mayor o menor que el objetivo.
Si el número del medio es mayor que el objetivo, comenzamos la búsqueda binaria nuevamente, pero esta vez en la mitad izquierda de la lista, es decir, desde el comienzo de la lista hasta el medio, no más allá de eso.
Si el número del medio es más pequeño que el objetivo, comenzamos la búsqueda binaria nuevamente, pero en la mitad derecha de la lista, es decir, desde el medio de la lista hasta el final de la lista.
3. Búsqueda de hash
Buscar una tabla hash es fácil y extremadamente rápido, solo encuentre el valor hash para el elemento que está buscando, luego vaya a ese índice y comience a buscar en la matriz hasta que encuentre lo que está buscando o llegue a un punto en blanco. El orden es bastante cercano a o (1), dependiendo de cuán llena esté su tabla hash.
4. Búsqueda de árbol binario
Buscar en un árbol binario es tan fácil como buscar en una tabla hash, pero generalmente es más lento (especialmente si el árbol está muy desequilibrado). Solo comienza en la raíz. Luego baje el subárbol izquierdo si la raíz es demasiado grande y el subárbol derecho si es demasiado pequeño. Repita hasta que encuentre lo que desea o el subárbol que desea no está allí. El tiempo de ejecución es O (log n) en promedio y O (n) en el peor de los casos.
