En las líneas 25 a 56 se declara el método
busquedaBinaria
. La clave de búsqueda se pasa al parámetro
elementoBusqueda
(línea 25). En las líneas 27 a 29 se calcula el índice del extremo
inferior
, el índice del
extremo
superior
y el índice
medio
de la porción del arreglo en la que el programa está buscando actualmente.
Al principio del método, el extremo
inferior
es
0
, el extremo
superior
es la longitud del arreglo menos
1
, y
medio
es el promedio de estos dos valores. En la línea 30 se inicializa la
ubicacion
del elemento en
-1
; el valor
que se devolverá si no se encuentra el elemento. En las líneas 32 a 53 se itera hasta que
inferior
sea mayor que
superior
(esto ocurre cuando no se encuentra el elemento), o cuando
ubicacion
no sea igual a
-1
(lo cual indica
que se encontró la clave de búsqueda). En la línea 43 se evalúa si el valor en el elemento
medio
es igual a
elemen-
toBusqueda
. Si esto es
true
, en la línea 44 se asigna
medio
a
ubicacion
. Después el ciclo termina y
ubicacion
se devuelve al método que hizo la llamada. Cada iteración del ciclo evalúa un solo valor (línea 43) y elimina la
mitad del resto de los valores en el arreglo (línea 48 o 50).
En las líneas 26 a 44 de la fi gura 16.5 se itera hasta que el usuario escriba
-1
. Para cada uno de los otros
números que escriba el usuario, el programa realiza una búsqueda binaria en los datos para determinar si coinciden
con un elemento en el arreglo. La primera línea de salida de este programa es el arreglo de valores
int
, en orden as-
cendente. Cuando el usuario indica al programa que busque el número
23
, el programa primero evalúa el elemen-
to medio, que es
42
(según lo indicado por el símbolo
*
). La clave de búsqueda es menor que
42
, por lo que el
programa elimina la segunda mitad del arreglo y evalúa el elemento medio de la primera mitad. La clave de bús-
queda es menor que
34
, por lo que el programa elimina la segunda mitad del arreglo, dejando sólo tres elementos.
Por último, el programa comprueba el
23
(que coincide con la clave de búsqueda) y devuelve el índice
1.
Efi ciencia de la búsqueda binaria
En el peor de los casos, el proceso de buscar en un arreglo ordenado de 1023 elementos sólo requiere 10 compa-
raciones cuando se utiliza una búsqueda binaria. Al dividir 1023 entre 2 en forma repetida (ya que después de
cada comparación podemos eliminar la mitad del arreglo) y redondear (porque también eliminamos el elemento
medio), se producen los valores 511, 255, 127, 63, 31, 15, 7, 3, 1 y 0. El número 1023 (2
10
– 1) se divide entre
2 sólo 10 veces para obtener el valor 0, que indica que no hay más elementos para probar. La división entre 2
1
// Fig. 16.5: PruebaBusquedaBinaria.java
2
// Usa la búsqueda binaria para localizar un elemento en un arreglo.
3
import
java.util.Scanner;
4
5
public class
PruebaBusquedaBinaria
6
{
7
public static void
main( String args[] )
8
{
9
// crea un objeto Scanner para recibir datos de entrada
10
Scanner entrada =
new
Scanner( System.in );
11
12
int
enteroABuscar;
// clave de búsqueda
13
int
posicion;
// ubicación de la clave de búsqueda en el arreglo
14
15
// crea un arreglo y lo muestra en pantalla
16
ArregloBinario arregloBusqueda =
new
ArregloBinario(
15
);
17
System.out.println( arregloBusqueda );
18
19
// obtiene la entrada del usuario
20
System.out.print(
21
"Escriba un valor entero (-1 para salir): "
);
22
enteroABuscar = entrada.nextInt();
// lee un entero del usuario
23
System.out.println();
24
25
// recibe un entero como entrada en forma repetida; -1 termina el programa
26
while
( enteroABuscar !=
-1
)
Figura 16.5
| La clase
PruebaBusquedaBinaria
. (Parte 1 de 2).
16.2 Algoritmos de búsqueda
693
16_MAQ_CAP_16_DEITEL.indd693
4/19/081:29:33AM