Estoy tratando de implementar la búsqueda binaria usando for loop en javascript pero falla algunos de los casos de prueba, a continuación está mi código
function binarySearch(arr, val){ let start = 0 let end = arr.length - 1 let middle = Math.floor((start + end)/2) for(let i = start; i<= end; i++){ if(val === arr[middle]) { return middle } if(val < arr[middle]){ end = middle - 1 } if(val > arr[middle]){ start = middle + 1 } middle = Math.floor((start + end)/2) } return -1 } // test case:1 console.log(binarySearch([5, 6, 9, 10, 13, 14, 18, 30, 34, 35, 37, 40, 44, 64, 79, 84, 86, 95, 96, 98, 99], 9)) // test case:2 console.log(binarySearch([1,3,4,5,6,7,8,9, 10], 10))Pasa el segundo caso de prueba pero falla miserablemente el primero. ¿Alguien puede arrojar algo de luz, por favor?
Tal como dijo Nishant, un bucle While sería adecuado en este caso, porque debe actualizar los valores de los índices izquierdo (inicio), derecho (final) y medio dentro del bucle.
Implementación iterativa de búsqueda binaria (en Java):
public int binarySearch(int[] array, int target) { var left = 0; var right = array.length - 1; while (left <= right) { var middle = (left + right) / 2; if (array[middle] == target) return middle; if (target < array[middle]) right = middle - 1; else left = middle + 1; } return -1; }Me di cuenta de por qué no usar "for loop" en este caso.
Es porque dentro del ciclo estoy asignando "inicio" un nuevo valor, pero surgen problemas cuando te encuentras con el hecho de que el valor de "i" sigue siendo el mismo valor de "inicio" previamente inicializado.
Lo mismo ocurre con, i <= end
Quiero decir que "i" no se reasigna a otra cosa que no sea i++. Me he dado cuenta del hecho de que, en estas situaciones, es mejor ir con la iteración del ciclo while en lugar del ciclo for, donde debe reiniciar el índice desde dentro del ciclo.