Busquedas en listas

BÚSQUEDA EN LISTAS: BÚSQUEDA BINARIA
Con mucha frecuencia los programadores trabajan con grandes cantidades de datos almacenados en arrays y registros, y por ello será necesario determinar si unarray contiene un valor que coincida con un cierto valor clave. El proceso de encontrar un elemento específico de un array se denomina búsqueda. En esta sección se examinarán dos técnicas de búsqueda:búsqueda lineal o secuencial, la técnica más sencilla, y búsqueda binaria o dicotómica, la técnica más eficiente.

Búsqueda binaria
La búsqueda secuencial se aplica a cualquier lista. Si la lista estáordenada, la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca delprincipio, del centro o del final dependiendo de la primera letra del primer apellido o de la palabra que busca. Se puede tener suerte y acertar con la página correcta; pero, normalmente, no será así yse mueve el lector a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con «J» y se está en la «L» se mueve uno hacia atrás. El proceso continúa hasta que se encuentra lapágina buscada o hasta que se descubre que la palabra no está en la lista. Una idea similar se aplica en la búsqueda en una lista ordenada. Se sitúa la lectura en el centro de la lista y se comprueba sila clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sigue la búsqueda uno en la mitad inferior o superior del elemento central de la lista. En general, silos datos de la lista están ordenados se puede utilizar esa información para acortar el tiempo de búsqueda.

Comparación de la búsqueda binaria y secuencial
La comparación en tiempo entre losalgoritmos de búsqueda secuencial y binaria se va haciendo espectacular a medida que crece el tamaño de la lista de elementos.

Esta tabla muestra la eficiencia de la búsqueda binaria comparada con...