binary Search to find closest float value to target number

Question

I have some question and Maybe One of you can help me, I have a float array and I won't find the closest float value to the target number(float)

I use a simple binary Search With javascript And from here I got stuck.

function binarySearch(arr, val, start = 0, end = arr.length - 1) {
    const mid = Math.floor((start + end) / 2);

    if(Math.abs(val - arr[mid]) < Math.abs(val - arr[mid + 1])){
        return mid;
    }

    if (start >= end) {
        return -1;
    }

    return val < arr[mid]
        ? binarySearch(arr, val, start, mid - 1)
        : binarySearch(arr, val, mid + 1, end);
}
let array = [0,0.03336667683886884,0.06673335367773768,0.10010003051660653,0.13346670735547536,0.1668333841943442,0.20020006103321306]

let result = binarySearch(array,'0.166833') //=> This value needs to be returned 0.1668333841943442

Answer 1

Your condition Math.abs(val - arr[mid]) < Math.abs(val - arr[mid + 1]) is wrong, you are always checking the left value is closer than the right value, so even for value 1 in array [10, 20, 30, 40], when you check number 20, 1 is closer to 20 than to 30 - incorrect result is then returned.

Also, you need to check the edge cases, the index mid + 1 may not be available. Also the value may be smaller than the minimum or larger than the maximum, so an infinite loop may occur.

Let me offer you this solution instead:

function binarySearch(arr, val, start, end) {
    // edge case: value of smaller than min or larger than max
    if(array[0] >= val) return 0;
    if(array[array.length - 1] <= val) return array.length - 1;
    
    while (start <= end) {
        let mid = Math.floor((end + start) / 2);
        
        // value is in interval from previous to current element
        if(val >= arr[mid - 1] && val <= arr[mid]) {
            return Math.abs(val - arr[mid - 1]) < Math.abs(val - arr[mid]) ? mid - 1 : mid;
        }
        else {
            if(arr[mid] < val) {
                start = mid + 1;
            } 
            else {
                end = mid - 1;
            }
        }
    }
    return -1;
}