CLASE 08 PRESENCIAL MEDIADA POR HERRAMIENTAS DE VIRTUALIDAD
ALGORITMO DE BÚSQUEDA BINARIA (BINARY SEARCH)
CURSO DE ESTRUCTURA DE DATOS - Código IS304 - Grupo 01
Programa de Ingeniería de Sistemas y Computación
Profesor Hugo Humberto Morales Peña
Miércoles 24 de Febrero de 2021
Algoritmo de Búsqueda Binaria (Binary Search)
En esta función se tienen como parámetros A que es un arreglo de elementos, i y j son índices que indican
las posiciones del primer y del último elemento en el rango de valores del arreglo sobre el cual se realiza la
búsqueda, y k es el elemento a buscar en el arreglo. Se exige como precondición para la Búsqueda Binaria que
los elementos del arreglo A tienen que estar ordenados de forma ascendente.
Algoritmo Binary Search
function BinarySearch( A, i, j, k )
1 if i > j then
2 return (−1) ∗ i − 1
3 else
i+j
4 m← 2
5 if (A[m] == k) then
6 return m
7 else
8 if (k > A[m]) then
9 BinarySearch( A, m + 1, j, k )
10 else
11 BinarySearch( A, i, m − 1, k )
Se tiene como postcondición para la Búsqueda Binaria que el valor devuelto por la función es un entero
correspondiente al índice del elemento que coincide con el valor buscado. Si el valor buscado no se encuentra,
entonces el valor devuelto es: -1 * (punto de inserción) - 1. El valor del punto de inserción es el índice del
elemento del arreglo donde debería encontrarse el valor buscado. La expresión: “-1 * (punto de inserción) - 1”
garantiza que el índice devuelto sera mayor o igual que cero solo si el valor buscado es encontrado.
1
Ejemplo
Realizar el paso a paso de la Búsqueda Binaria cuando se tiene el arreglo de elementos:
A[i] 2 4 7 9 10 11 13 14 17 30
i 1 2 3 4 5 6 7 8 9 10
y se manda a buscar el número 12.
Paso a paso del algoritmo Binary Search
BinarySearch( A, 1, 10, 12 )
i j k m
1 10 12 5
BinarySearch( A, 6, 10, 12 )
i j k m
6 10 12 8
BinarySearch( A, 6, 7, 12 )
i j k m
6 7 12 6
BinarySearch( A, 7, 7, 12 )
i j k m
7 7 12 7
BinarySearch( A, 7, 6, 12 )
i j k
7 6 12
return −8
La función BinarySearch devolvió un −8, como es un número negativo entonces el número 12 no se encuentra
presente en el arreglo. Recordar que −8 = −1 · puntoInsercion − 1, donde puntoInsercion = 7, con lo cual se
indica que el elemento 12 debería estar ubicado en la posición 7 del arreglo, pero dicho elemento no se encuentra
allí.
Complejidad en tiempo de ejecución del Algoritmo Binary Search
Sea T (n) la función que cuenta el total de operaciones que realiza el algoritmo Binary Search para determinar
si el número k se encuentra presente en el arreglo A el cual tiene n elementos.
T (1) = O(1)
n
T (n) = O(1) + T , para n ≥ 2, n ∈ Z+
| {z } 2
Costo de las líneas 1-7 | {z }
Costo de las líneas 8-11
n
T (n) = T 2 + O(1), para n ≥ 2, n ∈ Z+
Para poder resolver la relación de recurrencia primero se deben limpiar todas las notaciones computacionales y
considerar que n toma valores que son potencias de 2, por lo tanto tenemos:
T (1) = 1
n
T (n) = T 2 + 1, para n = 2m , m ≥ 1, m ∈ Z+
2
En el Ejemplo 4 de la clase anterior (clase 7) se resolvió esta relación de recurrencia, donde se obtuvo que en
términos de la variable original la solución de la relación de recurrencia es:
T (n) = log2 (n) + 1, para n = 2m , m ≥ 0, m ∈ N
Ahora toca aplicar sobre la solución de la relación de recurrencia la notación
computacional que fue borrada
de la relación de recurrencia, con lo cual obtenemos que T (n) = O log(n) , o dicho en palabras, tenemos que
en el peor de los casos la Búsqueda Binaria realiza log(n) operaciones sobre el arreglo A para determinar si el
elemento k se encuentra presente en el. Donde n es la cantidad de elementos que se encuentran almacenados en
el arreglo A.
Implementación del Algoritmo de Búsqueda Binaria (Binary Search)
# include < stdio .h >
# include < stdlib .h >
# include < math .h >
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* El valor devuelto por la funci ó n es un entero */
/* co rr e sp on d ie nt e al indice del elemento que */
/* coincide con el valor buscado . Si el valor */
/* buscado no se encuentra , entonces el valor */
/* devuelto es : - ( punto de inserci ó n ) - 1. El */
/* valor del punto de inserci ó n es el indice del */
/* elemento del vector donde deberia encontrarse */
/* el valor buscado . La expresion : */
/* " - ( punto de inserci ó n ) - 1" garantiza que el */
/* indice devuelto sera mayor o igual que cero */
/* solo si el valor buscado es encontrado . */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int binarySearch ( int A [] , int i , int j , int k )
{
int m , result = -1;
while ( i <= j )
{
m = ( i + j ) > >1; /* m = ( i + j ) /2; */
if ( A [ m ] == k )
{
result = m ;
break ;
}
else
{
if ( k > A [ m ])
i = m + 1;
else
j = m - 1;
}
}
if ( result == -1)
result = ( -1) * i - 1;
return result ;
}
int main ()
{
int A [100] , index , n , queries , idQuery , k , position ;
scanf ( " %d " , & n ) ;
for ( index = 1; index <= n ; index ++)
scanf ( " %d " , & A [ index ]) ;
scanf ( " %d " , & queries ) ;
3
for ( idQuery = 1; idQuery <= queries ; idQuery ++)
{
scanf ( " %d " , & k ) ;
position = binarySearch (A , 1 , n , k ) ;
if ( position >= 0)
printf ( " The element %d is in the array , position : %d \ n " , k , position ) ;
else
printf ( " The element %d is not in the array , insertion point : %d \ n " ,
k , -1 * position - 1) ;
}
return 0;
}
Figura 1: Salida del programa de la Búsqueda Binaria.
4
Asistentes a clase
Figura 2: Asistentes a la Clase 08 en el Google Meet (Febrero 24, 2021).