时间戳

首页 > 解决方案 > 二进制搜索以找到最接近目标数字的浮点值

javascript - 二进制搜索以找到最接近目标数字的浮点值

问题描述

我有一些问题，也许你们中的一个可以帮助我，我有一个浮点数组，我找不到最接近目标数的浮点值（浮点数）

我使用带有 javascript 的简单二进制搜索从这里我被卡住了。

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

标签： javascriptalgorithmecmascript-6binary-search

解决方案

你的条件Math.abs(val - arr[mid]) < Math.abs(val - arr[mid + 1])是错误的，你总是检查左边的值比右边的值更近，所以即使数组 [10, 20, 30, 40] 中的值 1，当你检查数字 20 时，1 更接近 20 而不是 30 - 然后返回不正确的结果。

此外，您需要检查边缘情况，索引mid + 1可能不可用。此外，该值可能小于最小值或大于最大值，因此可能会发生无限循环。

让我为您提供这个解决方案：

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

推荐阅读