Trimestre 2014 Primavera
Entrega: 30 de junio de 2014 a las 22:00.
El propósito de esta tarea es el de comparar dos métodos de búsqueda
en arreglos ordenados vistos en clase: búsqueda binaria y búsqueda
por interpolación. Dado un arreglo A ordenado de N enteros y un
elemento B, debes ejecutar ambos algoritmos para calcular cuántas
comparaciones hace cada uno. En el primer ejemplo de abajo, los dos
algoritmos hacen esto:
Búsqueda binaria comienza con el intervalo del 0 al 9,
compara el 5 con el dato en la posición 4 = (0+9)/2,
reduce su intervalo a 0 a 3, compara el 5 con el dato en
la posición 1 = (0+3)/2, reduce su intervalo a 2 a 3, compara
el 5 con el dato en la posición 2 = (2+3)/2 y termina. Por lo
tanto, hace 3 comparaciones.
Búsqueda por interpolación comienza con el intervalo
del 0 al 9, compara el 5 con el dato en la posición 1 =
0+(9-0)(5-2)/(29-2), reduce su intervalo a 2 a 9, compara
el 5 con el dato en la posición 2 = 2+(9-2)(5-5)/(29-5) y
termina. Por lo tanto, hace 2 comparaciones.
Escribe un programa busquedaNN
que lleve a cabo esta tarea.
La entrada al programa consiste de un renglón con un entero N,
seguido de un renglón con N datos enteros A[0], ..., A[N-1], seguido
de un entero B.
Puedes suponer que 1 <= N <= 100,000, que 0 <= A[0] <
A[1] < ... < A[N-1]<= 1,000,000 y que B sí está en el
arreglo A.
La salida del programa consiste de un renglón con dos enteros P y Q,
la cantidad de comparaciones hechas por búsqueda binaria y búsqueda
por interpolación.