I am trying to implement binary search using for loop in javascript but it fails some of the test cases, below is my code
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))
It passes the 2nd test case but miserably fails the 1st one. Can anyone throw some light, please?
Just like you said Nishant, a While-loop would be suitable in this case, because you should update the values of left(start), right(end) and middle indexes inside the loop.
Iterative implementation of Binary Search (in 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;
}
I realized why not use "for loop" in this case.
It is because inside the loop I'm assigning "start" a new value but problems arise when you come across the fact that the value of "i" remains the same previously initialized "start" value.
The same occurs with, i <= end
I mean "i" is not reassigned anything other than i++. I've realized the fact that under these situations it's better to go with the while loop iteration instead of for loop where you need to reinitialize index from inside the loop.