Contenido principal
Curso: Ciencias de la computación > Unidad 1
Lección 2: Búsqueda binariaImplementar la búsqueda binaria de un arreglo
Veamos cómo pensar acerca de la búsqueda binaria en un arreglo ordenado. Sí, JavaScript ya proporciona métodos para determinar si un elemento dado está en un arreglo y, si está, dar su ubicación (así como lo hacen muchos lenguajes de programación), pero queremos implementarlo nosotros mismos, para entender cómo puedes implementar dichos métodos. Aquí hay un arreglo de JavaScript de los primeros 25 números primos, en orden:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];Supón que queremos saber si el número 67 es primo. Si 67 está en el arreglo, entonces es primo.
También podemos querer saber cuántos primos son menores que 67. Si encontramos la posición del número 67 en el arreglo, podemos usar eso para averiguar cuántos primos menores existen.
La posición de un elemento en un arreglo se conoce como su índice. Los índices de los arreglos empiezan en 0 y aumentan hacia arriba. Si un elemento está en el índice 0 entonces es el primer elemento en el arreglo. Si un elemento está en el índice 3, entonces tiene 3 elementos antes que él en el arreglo.
Al mirar el siguiente ejemplo, podemos leer el arreglo de números primos de izquierda a derecha, uno a la vez, hasta que encontremos el número 67 (en la caja rosa) y ver que está en el índice 18 del arreglo. Mirar a través de los números en orden de esta manera es una búsqueda lineal.
Una vez que sabemos que el número primo 67 está en el índice 18, podemos identificar que es un primo. También podemos identificar rápidamente que hay 18 elementos que vienen antes del 67 en el arreglo, lo que significa que hay 18 números primos menores que 67.
¿Viste cuántos pasos tomó eso? Una búsqueda binaria podría ser más eficiente. Como el arreglo
primes contiene 25 números, los índices en el arreglo van de 0 a 24. Al usar nuestro pseudocódigo anterior, empezamos por hacer min = 0 y max = 24. El primer intento en la búsqueda binaria sería entonces en el índice 12 (que es (0 + 24) / 2). ¿primes[12] es igual a 67? No, primes[12] es 41.¿El índice que estamos buscando es mayor o menor que 12? Como los valores en el arreglo están en orden ascendente, y 41 < 67, el valor 67 debe estar a la derecha del índice 12. En otras palabras, el índice que estamos tratando de adivinar debe ser mayor que 12. Actualizamos el valor de
min a 12 + 1, o 13, y dejamos max sin cambio en 24.¿Cuál es el siguiente índice que intentamos? El promedio de 13 y 24 es 18.5, el cual redondeamos hacia abajo a 18, puesto que un índice de un arreglo debe ser un entero. Encontramos que
primes[18] es 67.El algoritmo de la búsqueda binaria se detiene en este punto, ya que ha encontrado la respuesta. Solo tomó dos intentos, en lugar de 19 intentos que le hubiera tomado a la búsqueda lineal. Lo puedes volver a ver paso por paso en la siguiente visualización:
Pseudocódigo
Acabamos de describir el algoritmo de la búsqueda binaria en español, haciendo cada paso en un ejemplo. Esa es una manera de hacerlo, pero una explicación en lenguaje humano puede variar en calidad. Puede ser muy corta o muy larga, y lo más importante, no siempre es tan precisa como debe ser. Podríamos adelantarnos a mostrarte la búsqueda binaria en un lenguaje de programación como JavaScript o Python, pero los programas contienen muchos detalles (debido a los requerimientos impuestos por el lenguaje de programación, o porque los programas tienen que manejar los errores causados por datos malos, errores del usuario o fallas en el sistema) que pueden hacer que sea difícil entender el algoritmo subyacente a partir de estudiar solo el código. Por eso preferimos describir los algoritmos en algo llamado pseudocódigo, que mezcla español con características que ves en los lenguajes de programación.
Aquí está el pseudocódigo para la búsqueda binaria, modificado para buscar en un arreglo. Las entradas son el arreglo, el cual llamamos
array; el número n de elementos en array; y target, el número que estamos buscando. La salida es el índice de target en array:- Sea
min = 0ymax = n-1. - Calcula
guesscomo el promedio demaxymin, redondeado hacia abajo (para que sea un entero). - Si
array[guess]es igual atarget, entonces detente. ¡Lo encontraste! Regresaguess. - Si el intento fue demasiado bajo, es decir,
array[guess] < target, entonces hazmin = guess + 1. - De lo contrario, el intento fue demasiado alto. Haz
max = guess - 1. - Regresa al paso 2.
Implementar pseudocódigo
Vamos a alternar entre español, pseudocódigo y JavaScript en estas lecciones, dependiendo de la situación. Como programador, debes aprender a entender pseudocódigo y ser capaz de convertirlo en tu lenguaje de preferencia; así que aunque aquí estemos usando JavaScript, debe ser directo para ti implementar el pseudocódigo al usar otros lenguajes.
¿Cómo convertiríamos ese pseudocódigo en un programa de JavaScript? Debemos crear una función, porque estamos escribiendo código que acepta una entrada y regresa una salida, y queremos que ese código sea reutilizable para diferentes entradas. Los parámetros de la función, vamos a llamarla
binarySearch, serán el arreglo y el valor objetivo, y el valor que regresa la función será el índice de la ubicación en donde se encontró el valor objetivo.Ahora vayamos al cuerpo de la función y decidamos cómo implementar eso. El paso 6 dice regresar al paso 2. Eso suena a un bucle. ¿Debería ser un bucle for o un bucle while? Si en verdad quisieras usar un bucle for, podrías, pero los índices de los intentos de la búsqueda binaria no van en el orden secuencial que hace que un bucle for sea conveniente. Primero podemos intentar el índice 12, y luego el 18, con base en algunos cálculos. Así que un bucle while es la mejor opción.
También hay un paso importante que falta en ese pseudocódigo que no importó en el juego de adivinar, pero que sí importa para la búsqueda binaria de un arreglo. ¿Qué debería pasar si el número que estás buscando no está en el arreglo? Vamos a empezar por averiguar qué índice debería regresar la función
binarySearch en este caso. Debería ser un número que no puede ser un índice válido en el arreglo. Usaremos -1, ya que no puede ser un índice válido para ningún arreglo. (En realidad, cualquier número negativo funcionaría).El número objetivo no está en el arreglo si ya no quedan intentos posibles. En nuestro ejemplo, supón que estamos buscando el número objetivo 10 en el arreglo
primes. Si estuviera ahí, el 10 estaría entre los valores 7 y 11, que están en los índices 3 y 4. Si sigues los valores de los índices para min y max a medida que se ejecuta la función binarySearch, encontrarías que eventualmente llegan al punto en donde min es igual a 3 y max es igual a 4. Entonces, el intento está en el índice 3 (ya que (3 + 4) / 2 es igual a 3.5, y redondeamos hacia abajo), y primes[3] es menor que 10, así que min se vuelve 4. Con ambos min y max iguales a 4, el intento debe estar en el índice 4, y primes[4] es mayor que 10. Ahora max se vuelve 3. ¿Qué significa que min sea igual a 4 y que max sea igual a 3? Significa que los únicos intentos posibles son por lo menos 4 y a lo más 3. ¡No hay tales números! En este punto, podemos concluir que el número objetivo, 10, no está en el arreglo primes y que la función binarySearch regresaría -1. En general, una vez que max se vuelve estrictamente menor que min, sabemos que el número objetivo no está en el arreglo ordenado. Aquí está el pseudocódigo modificado para la búsqueda binaria que maneja el caso en el cual el número objetivo no está presente:- Sea
min = 0ymax = n-1. - Si
max < min, entonces detente:targetno está enarray. Regresa-1. - Calcula
guesscomo el promedio demaxymin, redondeado hacia abajo (para que sea un entero). - Si
array[guess]es igual atarget, entonces detente. ¡Lo encontraste! Regresaguess. - Si el intento fue demasiado bajo, es decir,
array[guess] < target, entonces hazmin = guess + 1. - De lo contrario, el intento fue demasiado alto. Haz
max = guess - 1. - Regresa al paso 2.
Ahora que ya pensamos juntos en el pseudocódigo, vas a intentar implementar la búsqueda binaria. Está bien regresar y mirar el pseudocódigo; de hecho, es algo bueno, porque entonces tendrás una mejor comprensión de lo que significa convertir pseudocódigo en un programa.
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
function findBinary(arr, neddle) {
var min = 0,
max = arr.length - 1;
while (min <= max){
var guess = Math.floor((min+max) / 2);
if (arr[guess] === neddle ) return guess;
(arr[guess] < neddle) ? min = guess + 1 : max = guess - 1;
}
return -1;
}(16 votos)- Buenas, aqui esta el codigo en python por si les interesa:
from math import floor #metodo que te ayudara a redondear el promedio hacia abajo
def binariSearch(primos,target):
min=0
max=len(primos)-1
guess=int()
while True:
if min>max:
print("target no esta en el array")
return -1
pass
guess=floor((min+max)/2)
if primos[guess]==target:
print("numero encontrado")
print(primos[guess]," | ",target,": ",primos)
return guess
pass
elif primos[guess]<target:
min=guess+1
pass
else:
max=guess-1
pass
pass
return 0
primos=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print(binariSearch(primos,7))(8 votos) - Despues de ver las respuestas de otros, pude entender como aplicar el pseudocodigo, aqui dejo mi resultado.
/* Returns either the index of the location in the array,
or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
var intento = 0;
while (max >= min){
intento++;
guess = Math.floor((min+max)/2);
if (array[guess] === targetValue){
println(
"Intentos para encontrar el objetivo:" + intento
);
return guess;
}
else if (array[guess] < targetValue){
min = guess + 1;
}
else {
max = guess - 1;
}
println(guess);
}
return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
var result = doSearch(primes, 73);
println("Found prime at index " + result);
Program.assertEqual(doSearch(primes, 73), 20);
Program.assertEqual(doSearch(primes, 79), 21);
Program.assertEqual(doSearch(primes, 7), 3);(5 votos)
Una pregunta ¿Que es el ultimo valor?
Program.assertEqual(doSearch(primes, 79), 21);
Program.assertEqual(doSearch(primes, 7), 3);(1 voto)
- Hola. Estoy atrapado en el paso 3 del desafío. Pide que se escriba el número de intentos cuando ha encontrado el objetivo y que no se imprima el número de intentos en cada iteración. Definí la variable tries y coloque dentro de un condicional println("It took " + tries + " tries"); pero no me permite avanzar. ¿Alguna sugerencia?
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
var tries = 1;
while(min <= max){
guess = Math.floor((min+max)/2);
println(guess);
if (array[guess] === targetValue) {return guess;}
else if (array[guess] < targetValue) {min = guess+1;}
else {max = guess-1;}
tries = tries + 1;
if (max<=min) {println("It took " + tries + " tries");}
}
return -1;
};(4 votos)- No agregues texto de mas, solo imprime la variable. De igual forma analiza mejor tus verificaciones ya que parece que tienes una repetida por ahi.(1 voto)
- No tenia idea de que se necesitara conocer javascript para avanzar, ya que el desafio: busqueda lineal no lo pude llevar a cabo porque no conozco de lenguajes de programacion y la razon por la que decidi empezar este curso es porque un amigo me dijo que antes de aprender un lenguaje debo primero conocer de algoritmos, asi que ¿como se supone que avance?(2 votos)
Yo no estoy de acuerdo con tu amigo, porque primero debes de aprender las bases de algun lenguaje de programación, para poder aplicar lo que vayas aprendiendo de algoritmos, y así mejorar como programador.(4 votos)
Muchachos este es el codigo del desafio siguiente
/* Returns either the index of the location in the array,
or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
var intentos = 0;
while (max>=min) {
intentos++;
guess = Math.floor((max+min)/2);
if(array[guess]===targetValue) {
println("¡Ya lo Encontraste! " + guess);
println("Llevó " + intentos + " intentos");
return guess;
}
else if (array[guess]<targetValue) {
min = guess +1;
}
else {
max = guess-1;
}
/*if(max<=min){
}*/
}
return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
var result = doSearch(primes, 41);
println("Found prime at index " + result);
Program.assertEqual(doSearch(primes, 73), 20);
Program.assertEqual(doSearch(primes, 79), 21);
Program.assertEqual(doSearch(primes, 83), 22);(3 votos)
desafio
var doSearch = function (array, targetValue) {
var max = array.length - 1;
var min = 0;
var guess;
while (max >= min);
{
guess = Math.floor ((max+min)/2);
if(array[guess] === targetValue);
{
return guess;
}
else if (array[guess] < targetValue);
{
min = guess + 1;
}
else {
max = guess - 1;
}
}
return -1;
}(3 votos)- buenos días he intentado al desafió?(2 votos)
/* Returns either the index of the location in the array,
or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var i = 0;
var guess;
while(min <= max){
guess = Math.floor((min + max) / 2);
i++;
println("posicion "+ guess);
if(array[guess] === targetValue){
println("adivinasre el número en " + i);
return guess;
}
else if(array[guess] < targetValue){
min = guess + 1;
}
else{
max = guess - 1;
}
}
return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
var result = doSearch(primes, 73);
println("Found prime at index " + result);
Program.assertEqual(doSearch(primes, 73), 20);
Program.assertEqual(doSearch(primes, 7), 3);
Program.assertEqual(doSearch(primes, 2), 0);(2 votos)def binary_search(lista, clave):
minimo = 0
maximo = len(lista) - 1
while(maximo >= minimo):
res = int((minimo + maximo)/2)
if lista[res] == clave:
return res
elif lista[res] < clave:
minimo = res + 1
else:
maximo = res - 1
return -1(2 votos)