Algoritmo de busqueda

Cuestiones generales

La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamentealmacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos debúsqueda tienen dos finalidades:

- Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.
- Si el elemento está en el conjunto, hallar la posición en la que se encuentra.En este apartado nos centramos en la búsqueda interna. Como principales algoritmos de búsqueda en arrays tenemos la búsqueda secuencial, la binaria y la búsqueda utilizando tablas de hash.Búsqueda secuencial

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 2 = 1998002-1998000
...
1998-399 --> 399 = 1998399-1998000
1999-000 --> 400 = 1999000-1998000+400
...
yyyy-nnn --> N = yyyynnn-1998000+(400*(yyyy-1998))

Aritmética modular: elíndice de un 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 elproblema de que cuando hay N+1 elementos, al menos un índice es señalado por dos elementos (teorema del palomar). A este fenómeno se le llama colisión, y es tratado más adelante. Si el número N es el 13,los números siguientes quedan transformados en:
13000000 --> 0
12345678 --> 7
13602499 --> 1
71140205 --> 6
73062138 --> 6

Mitad del cuadrado: consiste en elevar al cuadrado la clave y cogerlas cifras centrales. Este método también presenta problemas de colisión:
123*123=15129 --> 51
136*136=18496 --> 84
730*730=532900 --> 29
301*301=90601 --> 06
625*625=390625 --> 06...