Algoritmos Básicos de Búsqueda

I. Búsqueda Secuencial (Sequential Search)

1. También conocido como la Búsqueda Lineal (Linear Search).

2. Puede usarse con arreglos que no estén ordenados.

3. Consiste en buscar un valor (la clave o key) comparándolo secuencialmente con cada elemento del arreglo hasta que éste se encuentre, o hasta que se llegue al final del arreglo.

4. La existencia se puede asegurar desde el momento que la clave es localizada, pero no podemos asegurar la no existencia hasta no haber examinado todos los elementos del arreglo.

5. Es un algoritmo de complejidad O(n) porque la cantidad de elementos examinados en el peor de los casos es directamente proporcional al tamaño del arreglo.

6. Ejemplos asumiendo el arreglo [10, 20, 30, 40, 50, 60, 70] de 7 elementos:

a. Si se busca el 30, se examinan los siguientes elementos: 10, 20 y 30.

b. Si se busca el 60, se examinan los siguientes elementos: 10, 20, 30, 40, 50 y 60.

c. Si se busca el 25, se examinan los siguientes elementos: 10, 20, 30, 40, 50, 60 y 70, concluyendo que el 25 no se encuentra.

d. Si se busca el 65, se examinan los siguientes elementos: 10, 20, 30, 40, 50, 60 y 70, concluyendo que el 65 no se encuentra.

II. Búsqueda Binaria (Binary Search)

1. Sólo puede usarse con arreglos ordenados.

2. Consiste en buscar un valor (la clave) comparándolo con el elemento central del arreglo. Puede ocurrir uno de los siguientes:

a. La clave es menor que el elemento central: se busca la clave en la porción del arreglo que va desde el inicio del arreglo hasta justo antes del elemento central.

b. La clave es mayor que el elemento central: se busca la clave en la porción del arreglo que va desde justo después del elemento central hasta el final del arreglo.

c. La clave es igual al elemento central: se puede asegurar su existencia.

3. Se revisan porciones cada vez más pequeñas hasta que se encuentra la clave en el elemento central o hasta que se obtenga una porción de un solo elemento. Si la clave no se encuentra dentro de esta última porción, se deduce que la clave no se encuentra en el arreglo.

4. Es un algoritmo de complejidad O(log₂ n) porque cada iteración parte a la mitad el espacio de búsqueda por lo que progresivamente hay menos trabajo que hacer.

5. Ejemplos asumiendo el arreglo [10, 20, 30, 40, 50, 60, 70] de 7 elementos:

a. Si se busca el 20, se examinan los siguientes elementos: 40 y 20.

b. Si se busca el 40, se examina el siguiente elemento: 40.

c. Si se busca el 60, se examinan los siguientes elementos: 40 y 60.

d. Si se busca el 5, se examinan los siguientes elementos: 40, 20 y 10, concluyendo que el 25 no se encuentra.

e. Si se busca el 25, se examinan los siguientes elementos: 40, 20 y 30, concluyendo que el 25 no se encuentra.

f. Si se busca el 45, se examinan los siguientes elementos: 40, 60 y 50, concluyendo que el 45 no se encuentra.

g. Si se busca el 75, se examinan los siguientes elementos: 40, 60 y 70, concluyendo que el 75 no se encuentra.