Algoritmo 11.5.1 Búsqueda binaria [El objetivo de este algoritmo es buscar un elemento x en un arreglo ascendente de elementos a[1], a[2], , a[n]. ...

Algoritmo 11.5.1 Búsqueda binaria [El objetivo de este algoritmo es buscar un elemento x en un arreglo ascendente de elementos a[1], a[2], , a[n]. Si se encuentra x, la variable índice es igual al índice del elemento del arreglo en donde x fue localizado. Si x no se encuentra, la variable índice continúa con su valor inicial, que es 0. Las variables inf y sup denotan los índices inferior y superior del arreglo bajo análisis]. Entrada: n [un entero positivo], a[1], a[2], , a[n] [un arreglo de datos dados en orden ascendente], x [un dato del mismo tipo de datos como los elementos del arreglo] Cuerpo del algoritmo índice : 0, inf : 1, sup : n [Calcule el índice medio del arreglo, med. Compare x con a[med]. Si los dos coinciden, la búsqueda ha sido exitosa. Si no, repita el proceso para el subarreglo inferior o superior ya sea dando a sup el nuevo valor med ฀ 1 o dando a inf el nuevo valor med 1. Cada iteración del bucle disminuye el valor de sup o incrementa el valor de inf. Así, si las iteraciones no son detenidas por el éxito en el proceso de búsqueda, eventualmente el valor de sup será menor que el valor de inf. Este hecho detiene el proceso iterativo e indica que x no es un elemento del arreglo.] while (sup inf e índice 0) med inf sup 2 if a[med] x then índice : med if a[med] x then sup : med ฀ 1 else inf : med 1 end while [Si índice tiene el valor 0 en este punto, entonces x no está en el arreglo. De otra forma, índice da el índice del elemento del arreglo en donde se localiza x.] Salida: índice [un entero no-negativo] Ejemplo 11.5.1 Seguimiento del algoritmo de búsqueda binaria Siga la acción del algoritmo 11.5.1 sobre las variables índice, inf, sup, med y los valores de x dados en a) y b) para el arreglo de entrada a 1 Ann a 2 Dawn a 3 Erik a 4 Gail a 5 Juan a 6 Matt a 7 Max a 8 Rita a 9 Tsuji a 10 Yuen donde se utiliza el ordenamiento alfabético para comparar elementos del arreglo. a. x Max b. x Sara Solución a. índice 0 7 inf 1 6 7 sup 10 7 med 5 8 6 7 b. índice 0 inf 1 6 9 sup 10 8 med 5 8 9 al bucle while del algoritmo de búsqueda binaria, entonces después de una iteración no exitosa del bucle, la entrada a la siguiente iteración es un arreglo de longitud a lo más k 2 . Solución Considere qué ocurre cuando se introduce un arreglo de longitud k al bucle while en el caso en donde x a[med]: a inf a inf 1 a med ฀1 a med a med 1 a sup฀1 a sup. nueva entrada al bucle while si x < a[med] elemento medio nueva entrada al bucle while si x > a[med] Como el arreglo de entrada tiene longitud k, el valor de med depende de si k es impar o par. En ambos casos, acoplamos los elementos del arreglo con los enteros de 1 a k y analizamos las longitudes de los subarreglos izquierdo y derecho. En el caso de k impar, los subarreglos izquierdo y derecho tienen longitud k 2 . En el caso k par, el subarreglo izquierdo tiene longitud k 2 1 y el derecho tiene longitud k 2 . En la figura 11.5.3 se muestra el razonamiento implicado en estos resultados. un arreglo de longitud k 2 . Así el máximo número de iteraciones del bucle es 1 más que el máximo número necesario para ejecutar un arreglo de entrada de longitud k 2 . En símbolos k 1 k 2 1 1También Porque para cada arreglo de entrada de longitud 1 (inf sup), el bucle while itera sólo una vez. Ahora que se ha encontrado una relación de recurrencia para 1, 2, 3, , se puede emplear la iteración para sugerir una fórmula explícita. Ejemplo 11.5.4 Una fórmula explícita para 1, 2, 3, Aplique iteración a la relación de recurrencia encontrada en el ejemplo 11.5.3 para inferir una fórmula explícita para 1, 2, 3, .