为什么我的 Python 中的浮点数二分搜索实现失败？

Question

我正在Python中为包含浮点数的排序列表实现二分搜索算法。但是，由于精度问题，该算法并不总是返回某些值的正确索引。 这是我的代码

def binary_search(arr, target):
   low, high = 0, len(arr) - 1
   while low <= high:
       mid = (low + high) // 2
       if abs(arr[mid] - target) < 1e-9:
           return mid
       elif arr[mid] < target:
           low = mid + 1
       else:
           high = mid - 1
   return -1

这是测试用例

arr = [0.1, 0.2, 0.3, 0.4, 0.5]
target = 0.3
print(binary_search(arr, target))  # Expected: 2, but got -1

我尝试过调整容差（1e-9）来比较浮点数并使用 math.isclose() 进行比较，但问题仍然存在。

为什么二分查找对于浮点数会失败？ Python 中是否有特定的技术或库可以更好地处理此类用例的精度？

Answer 1

我认为浮点数问题是由于设备上浮点数表示的精度有限造成的。

尝试用这两种方法

1. 使用 math.isclose() 进行比较 该函数旨在比较两个浮点数，考虑相对和绝对容差。

2. 检查您的binary_search实现 确保它在算法中正确使用 math.isclose() 。

我认为实现代码还需要修改如下：

import math

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if math.isclose(arr[mid], target, rel_tol=1e-9, abs_tol=1e-9):
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Test case
arr = [0.1, 0.2, 0.3, 0.4, 0.5]
target = 0.3
print(binary_search(arr, target))  # Expected: 2

希望对你有帮助