Métodos De Búsqueda

Métodos de búsqueda

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.
Siendo el array de una dimensión o lista unaestructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: búsqueda secuencial, búsqueda binaria, búsqueda hash y búsqueda extrema.

Búsqueda secuencial
La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elementoa elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidadde que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde sereduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array.
for(i=j=0;i> 0
05210801 −05210800>>>> 1
05210802 −05210800>>>> 2
…
05210899 −05210800>>>> 99
2.- Aritmética modular: El índice deun número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que dos o más elementos pueden producir el mismo residuo y un índice puede ser señalado por varios elementos. A este fenómeno se le llama colisión. Si el número N es el 7, los números siguientesquedan transformados en:
1679 >>> 6
4567 >>> 3
8471 >>> 1
0435 >>> 1
5033 >>> 0
Mientras mas grande sea número de elementos es mejor escoger un número primo mayor para seccionar el arreglo en más partes. El número elegido da el número de partes en que se secciona el arreglo, y las cada sección esta compuesta por todos los elementos que arrojen el mismo residuo, y mientras mas pequeñas sean lassecciones la búsqueda se agilizara mas que es lo que nos interesa.
3.- Mitad del cuadrado: Consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión:
709^2=502681 → 26
456^2=207936 → 79
105^2=11025 → 10
879^2=772641 → 26
619^2=383161 → 31
Nota: en caso de que la cifra resultante sea impar se toma el valor número y el anterior.4.- Truncamiento: Consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de elementos, se pueden tomar el segundo, el cuarto y el sexto para formar un nuevo número:
5700931 >>> 703
3498610 >>> 481
0056241 >>> 064
9134720 >>> 142
5174829 >>> 142
5.- Plegamiento:Consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos el número de 7 cifras en 2, 2 y 3 cifras y se suman, dará otro número de tres cifras (y si no, se toman las tres últimas cifras):
5700931 >>> 57 + 00 + 931 = 988
3498610 >>> 34 + 98 + 610 = 742
0056241 >>> 00 + 56 + 241 = 297...