Prgramacion

Cuestiones generales
La bsqueda de un elemento dentro de un array es una de las operaciones ms importantes en el procesamiento de la informacin, y permite la recuperacin de datos previamentealmacenados. El tipo de bsqueda se puede clasificar como interna o externa, segn el lugar en el que est almacenada la informacin (en memoria o en dispositivos externos). Todos los algoritmos de bsquedatienen 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 posicin en la que se encuentra.
En esteapartado nos centramos en la bsqueda interna. Como principales algoritmos de bsqueda en arrays tenemos la bsqueda secuencial, la binaria y la bsqueda utilizando tablas de hash.
Bsqueda secuencial
Consisteen 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 1 = 1998001-19980001998-002 --> 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 índicede 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 el problemade 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, losnú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 coger lascifras 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
· Truncamiento:...