Cómo implementar la búsqueda binaria en JavaScript

https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-search

Estaba siguiendo el pseudo código para implementar el algoritmo en el enlace pero no sé qué está mal con mi código.

Aquí está mi código:

/* 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; while(min < max) { guess = (max + min) / 2; if (array[guess] === targetValue) { 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, 2); println("Found prime at index " + result); //Program.assertEqual(doSearch(primes, 73), 20); 

Para obtener un valor de una matriz, debe especificar un número entero como la array[1] . array[1.25] volverá undefined en su caso.

Para que funcione, simplemente agregué Math.floor en tu interior para asegurarte de que obtengamos un número entero.

EDITAR: como @KarelG señala, usted también necesita agregar <= en su bucle while. Esto es para situaciones donde min y max han convertido en lo mismo, en cuyo caso guess === max === min . Sin el <= el bucle no se ejecutaría en estas situaciones y la función devolvería -1 .

 function (array, targetValue) { var min = 0; var max = array.length - 1; var guess; while(min <= max) { 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; } 

Puedes usar cualquiera de Math.floor , Math.ceil y Math.round .

Espero que esto haya sido de poca ayuda, no soy muy bueno explicando, pero haré todo lo posible para explicarlo.

En su código, cuando min es igual a max, el bucle termina. Pero en este escenario no está comprobando si array[min] == targetValue

Así que cambiar el código a esto probablemente solucionará tu problema

 /* 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; while(min <= max) { 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; }; 

Enlace JSFiddle: http://jsfiddle.net/7zfph6ks/

Espero eso ayude.

PS: el único cambio en el código es esta línea: while (min <= max)

solo tienes que descomentar el Program.assertEqual de esta manera:

 Program.assertEqual(doSearch(primes, 73), 20); 

así no :

 //Program.assertEqual(doSearch(primes, 73), 20); 

Si alguien todavía está buscando la respuesta, necesitas hacerlo (max> = min)

 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;