7.2 Métodos de Búsqueda 169 1) Búsqueda del número –5. En la primera asignación resultan min 1, max 9, medio 5, de donde x[medio] 1, que es mayor que el dato –5. Por lo tanto, hay que seguir buscando hacia la izquierda, lo que significa trasladar max a centro – 1, o sea max 4. Promediando con min queda medio (1 + 4) div 2 = 2, y precisamente en la posición 2 se encuentra –5, por lo que la búsqueda termina aquí. 2) Búsqueda del número 23 La primera vez, siendo medio la posición 5, resulta 23 >1, y hay que buscar a la derecha, o sea hacermin medio +1 = 6. Promediando, medio (6 + 9) div 2 = 7, donde tampoco está el dato. Como 23 > 7, hacemos min 8, medio (8 + 9) div 2 = 8, no está el dato, llevamos min a 9, y centro (9 + 9) div 2 = 9. La posición 9 contiene el valor 7, que no es el dato 23. Como 23 > 7, ahora queda medio centro +1 = 10. Se han cruzado izq y der, y al quedar vacío el intervalo de búsqueda la condición establecida en el “Repetir mientras” hace que la búsqueda finalice sin éxito. 3) Búsqueda del número 7. La respuesta del método a este caso deberá ser 9, es decir, la posición del número 7 en el arreglo.Realizando la misma metodología que antes, la posición media del arreglo es 5, medio=(min+max) div 2, donde X[medio] es 1, que es menor que el valor 7. Por lo tanto, hay que seguir buscando hacia la derecha, y como la posición 5 ya se examinó, el nuevo intervalo de búsqueda resulta [medio+1, max]= [6,9], donde min = medio+1.Calculando nuevamente el medio del nuevo intervalo, medio=(6 + 9) div 2 = 7, donde X[medio] es 4, que es menor que el valor 7. Por lo cual habrá que correr el intervalo de búsqueda hacia la derecha, y como la posición 7 ya se examinó, el nuevo intervalo de búsqueda resulta [medio+1, max]=[8,9], donde min = medio+1. Calculando nuevamente el medio del nuevo intervalo, medio=(8 + 9) div 2 = 8, donde X[medio] es 6, menor que el valor 7. Por lo cual habrá que correr el intervalo de búsqueda hacia la derecha, y como la posición 8 ya se examinó, el nuevo intervalo de búsqueda resulta [medio+1, max]=[9,9]. Calculando nuevamente el medio del nuevo intervalo, medio=(9 + 9) div 2 = 9. Precisamente en la posición 9 se encuentra el valor 7 buscado, por lo tanto la búsqueda termina aquí. 7.2.4 Cantidad de comparaciones efectuadas Razonando en forma simplificada, como lo hicimos con el método Quick sort, pensemos que la cantidad de componentes del arreglo es n = 2 elevado k. Luego de la primera operación, o sea del primer cálculo y comparación en el centro, la longitud del arreglo donde hay que seguir buscando se redujo a la mitad, 2elevadok-1. Luego de la segunda, la longitud es 2 elevado k-2, y después de k operaciones, la longitud es 2 elevado 0 = 1, donde se efectúa todavía una comparación más (eventualmente el proceso podría haberse detenido antes, de coincidir el dato en alguno de los centros intermedios). En conclusión, la cantidad promedio de comparaciones es k + 1 = (log2 n) +1. Si n >>1, el 1 puede despreciarse, y se dice que el algoritmo de búsqueda dicotómica es del orden de log2 n. Por ejemplo, buscar en forma secuencial un abonado en una guía de 100.000 teléfonos requiere efectuar entre 1 y 100.000 comparaciones, como promedio 50.000. En una búsqueda dicotómica, en cambio, esta cantidad se reduce a log2 100.000 17 comparaciones.
Created with BuildVu