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

Question

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

我使用 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

Answer 1

你的停止条件被打破。在您的示例中，如果您输入以下数组：

[0.3, 0.5, 0.8, 2.0]

你在开始时有：

arr[mid] = 0.5
arr[mid + 1] = 0.8

因此，如果您将 val = 0.1 提供给您的算法，您将拥有：

Math.abs(val - arr[mid]) = 0.4
Math.abs(val - arr[mid + 1]) = 0.7

因此，尽管您期望 0.3 的索引，但您将 return 0.5 的索引。

解决您的问题的伪想法是：

if array contains 1 element => return element
else if array contains 2 elements => return element closest to val.
else if val < array[mid] => recurse on first half
else if val > array[mid] => recurse on second half

Answer 2

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

此外，您需要检查边缘情况，索引 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;
}

Answer 3

看来你打错了。您不应该 return mid 索引，而是 array[mid]:

中的数组项

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 arr[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];
console.log(binarySearch(array,'0.166833')) // 0.1668333841943442

Answer 4

我找到了这个解决方案，但我需要 return 正确值的索引

function binarySearch(arr, target, lo = 0, hi = arr.length - 1) {
   if (target < arr[lo]) {return arr[0]}
   if (target > arr[hi]) {return arr[hi]}
   
   const mid = Math.floor((hi + lo) / 2);

   return hi - lo < 2 
     ? (target - arr[lo]) < (arr[hi] - target) ? arr[lo] : arr[hi]
     : target < arr[mid]
       ? binarySearch(arr, target, lo, mid)
       : target > arr[mid] 
         ? binarySearch(arr, target, mid, hi)
         : arr[mid]
}

let array = [0, 0.03336667683886884, 0.06673335367773768, 0.10010003051660653,0.13346670735547536, 0.1668333841943442, 0.20020006103321306,30.01]; 
    
console.log(binarySearch(array,0.03336))

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

binary Search to find closest float value to target number

javascript

algorithm

binary-search

ecmascript-6