P.03 Búsqueda binaria

En una lista ordenada de n elementos, una manera de hallar un valor dado es recorrer exhaustivamente la lista.
Un elemento dado, entonces, será hallado recorriendo -en promedio- n/2 elementos (demuestre el aserto).
Es decir, en una lista de 1000 elementos, hallar uno cualquiera exigirá recorrer -reitero, en promedio- 500 elementos.

Siendo una lista ordenada, podemos efectuar una búsqueda binaria.
Consiste, básicamente, en ir dividiendo la lista en mitades, hasta acotar la lista a dos o un elemento.

Por ejemplo, en una lista ordenada de números impares que parte de 1 (y termina en 1999), hallar el número x = 599.

Declaro las variables punto medio (pm), punto inicial (pi), punto final (pf).

pi = 1
pf = 1999

while
pm = (pi + pf) / 2 = (1 + 1999) / 2 = 1000

Si x > pm, entonces pi = pm, y vuelvo al while

Si x < pm, entonces pf = pm, y vuelvo al while

Si x = pm, hallado el elemento.


La búsqueda binaria implica recorrer log(2) 1000 = 8 elementos ( 2**8 = 1024 ). Es decir, en vez de hacer 500 búsquedas, hago 8 búsquedas...

Ejercicio:

Construya un programa Java que permita ingresar un número y hallarlo en un arreglo de de 500 enteros con la progresión cuyo término general es 2n + 1 y que parte de 1. (Determine el término 500).