la clave de búsqueda, el algoritmo termina. Suponiendo que el arreglo se ordene en forma ascendente, entonces
si la clave de búsqueda es menor que el elemento de en medio, no puede coincidir con ningún elemento en la
segunda mitad del arreglo, y el algoritmo continúa sólo con la primera mitad (es decir, el primer elemento hasta,
pero sin incluir, el elemento de en medio). Si la clave de búsqueda es mayor que el elemento de en medio, no
puede coincidir con ninguno de los elementos de la primera mitad del arreglo, y el algoritmo continúa sólo con la
segunda mitad del arreglo (es decir, desde el elemento después del elemento de en medio, hasta el último elemen-
to). Cada iteración evalúa el valor medio de la porción restante del arreglo. Si la clave de búsqueda no coincide
con el elemento, el algoritmo elimina la mitad de los elementos restantes. Para terminar, el algoritmo encuentra
un elemento que coincide con la clave de búsqueda o reduce el subarreglo hasta un tamaño de cero.
Como ejemplo, considere el siguiente arreglo ordenado de 15 elementos:
2 3 5 10 27 30 34 51 65 77 81 82 93 99
y una clave de búsqueda de 65. Un programa que implemente el algoritmo de búsqueda binaria primero com-
probaría si el 51 es la clave de búsqueda (ya que 51 es el elemento de en medio del arreglo). La clave de búsqueda
(65) es mayor que 51, por lo que este número se descarta junto con la primera mitad del arreglo (todos los elemen-
tos menores que 51). A continuación, el algoritmo comprueba si 81 (el elemento de en medio del resto del arreglo)
coincide con la clave de búsqueda. La clave de búsqueda (65) es menor que 81, por lo que se descarta este núme-
ro junto con los elementos mayores de 81. Después de sólo dos pruebas, el algoritmo ha reducido el número
de valores a comprobar a tres (56, 65 y 77). Después el algoritmo comprueba el 65 (que coincide induda-
blemente con la clave de búsqueda), y devuelve el índice del elemento del arreglo que contiene el 65. Este
algoritmo sólo requirió tres comparaciones para determinar si la clave de búsqueda coincidió con un elemento
del arreglo. Un algoritmo de búsqueda lineal hubiera requerido 10 comparaciones. [
Nota: en este ejem-
plo hemos optado por usar un arreglo con 15 elementos, para que siempre haya un elemento obvio en medio
del arreglo. Con un número par de elementos, la parte media del arreglo se encuentra entre dos elementos.
Implementamos el algoritmo para elegir el menor de esos dos elementos].
La fi gura 16.4 declara la clase
ArregloBinario
. Esta clase es similar a
ArregloLineal
: tiene dos variables de
instancia
private
, un constructor, un método de búsqueda (
busquedaBinaria
), un método
elementosRestan-
tes
y un método
toString
. En las líneas 13 a 22 se declara el constructor. Una vez que se inicializa el arreglo con
valores
int
aleatorios de
10 a 99
(líneas 18 y 19), en la línea 21 se hace una llamada al método
Arrays.sort
en
el arreglo
datos
. El método
sort
es un método
static
de la clase
Arrays
, que ordena los elementos en un arreglo
en orden ascendente de manera predeterminada; una versión sobrecargada de este método nos permite cambiar la
forma de ordenar los datos. Recuerde que el algoritmo de búsqueda binaria sólo funciona en un arreglo ordenado.
1
// Fig. 16.4: ArregloBinario.java
2
// Clase que contiene un arreglo de enteros aleatorios y un método
3
// que utiliza la búsqueda binaria para encontrar un entero.
4
import
java.util.Random;
5
import
java.util.Arrays;
6
7
public class
ArregloBinario
8
{
9
private int
[] datos;
// arreglo de valores
10
private static
Random generador =
new
Random();
11
12
// crea un arreglo de un tamaño dado y lo llena con enteros aleatorios
13
public
ArregloBinario(
int
tamanio )
14
{
15
datos =
new int
[ tamanio ];
// crea espacio para el arreglo
16
17
// llena el arreglo con enteros aleatorios en el rango de 10 a 99
18
for
(
int
i =
0
; i < tamanio; i++ )
19
datos[ i ] =
10
+ generador.nextInt(
90
);
20
21
Arrays.sort( datos );
Figura 16.4
| La clase
ArregloBinario
. (Parte 1 de 2).
16.2 Algoritmos de búsqueda
691
16_MAQ_CAP_16_DEITEL.indd691
4/19/081:29:32AM