alternative solution to binary search just as good?

Question

for a binary search questions I came up with the following solution:

function binarySearch(arr,numba){
    
    var left = 0
    var right = arr.length - 1
    
    while (left <= right){
        let middle = Math.floor((left+right)/2)
        if (arr[middle] < numba){
            left ++;
            
        }
        else if (numba < arr[middle]){
            right -- ;
            
        }
        else if (numba === arr[middle]){
            return middle
        }
    }
    return -1
}

but the suggested solution is :

function binarySearc(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

Is the second solution better than what I have in any way or are they essentially the same thing?

Answer 1

Yes, the second solution is better. It's the only one that's actually performing a binary search (computational complexity of O(log n)). See below snippet to see how many times the middle needs to be recalculated using the suggested solution:

function binarySearc(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    let iterCount = 0;
    while(arr[middle] !== elem && start <= end) {
        iterCount++;
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    console.log('iterCount', iterCount);
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

const arr = Array.from({ length: 100 }, (_, i) => i);
binarySearc(arr, 30);

In contrast, your solution requires reassigning middle on the order of O(n) times - it's not actually doing a binary search.

function binarySearch(arr,numba){
    
    var left = 0
    var right = arr.length - 1
    
    let iterCount = 0;
    while (left <= right){
        iterCount++;
        let middle = Math.floor((left+right)/2)
        console.log(middle);
        if (arr[middle] < numba){
            left ++;
            
        }
        else if (numba < arr[middle]){
            right -- ;
            
        }
        else if (numba === arr[middle]){
            console.log('iterCount', iterCount);
            return middle
        }
    }
    return -1
}

const arr = Array.from({ length: 100 }, (_, i) => i);
binarySearch(arr, 30);

For example, with an array of length 100, you start with left of 0 and right of 99, and then on each iteration inside the loop, you either increment left by 1 or decrement right by 1. True binary search would involve incrementing or decrementing to cut down the remaining elements to be searched by about half - for example, to start at 0-99, then go to 0-49, then 24-49, then 24-36, and so on. That way you get to the target (if it exists) much faster than 0-99, then 0-98, then 0-97, etc.