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?

CodePudding user response：

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.

CodePudding user response：

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;
}