Búsqueda

BÚSQUEDA SECUENCIAL

Esta búsqueda es aplicable a una tabla organizada, ya sea como vector o como una lista ligada.
   

è Eficiencia: nº comparaciones à O(n)

Métodos de búsqueda con reordenamiento:
   

       Moverse-al-frente: el registro recuperado se elimina de su localización actual de la lista y se coloca a la cabeza de la misma.

       Transposición: un registro recuperado se intercambia con el que lo precede de manera inmediata.

BÚSQUEDA BINARIA

Se compara el argumento con la clave del elemento medio de la tabla. Si no son iguales, se busca de manera similar en la mitad superior o inferior de la tabla.
   

è Eficiencia: O(log n)

BÚSQUEDA POR INTERPOLACIÓN

Si las claves están distribuidas de manera uniforme, el método puede ser aún más eficiente que la búsqueda binaria.

Búsqueda de clave (key) en la posición prevista (mid) por interpolación:

è Eficiencia: O(log (log n) )

ÁRBOLES BINARIOS DE BÚSQUEDA

Para determinar si “k” está presente en el árbol la comparamos con la clave situada en la raíz “r”. Si k < r buscaremos en el subárbol izquierdo. Si k > r buscaremos en el subárbol derecho.