Haskell是否存在接收比较函数的通用二分搜索函数？

好问题！Haskell的标准库（base包）里并没有直接提供完全符合你指定类型签名的通用二分搜索函数，但我们可以轻松实现一个，完美匹配你描述的需求——接收比较函数、返回LT的起始值、返回GT的终止值，最终定位到让比较函数返回EQ的目标值。

针对整数类型的实现 #

首先，我们先实现适用于整数类型的版本（匹配你给出的示例场景）：

-- 安全计算整数中点，避免直接相加导致的溢出问题
midpoint :: Integral a => a -> a -> a
midpoint low high = low + (high - low) `div` 2

binarysearch :: Integral a => (a -> Ordering) -> a -> a -> a
binarysearch f low high = case f mid of
    EQ -> mid                     -- 找到目标值，直接返回
    LT -> binarysearch f mid high -- f(mid)为LT，说明目标在mid到high之间
    GT -> binarysearch f low mid  -- f(mid)为GT，说明目标在low到mid之间
  where
    mid = midpoint low high

测试示例 #

用你给出的例子验证一下：

-- 示例1：查找100，比较函数直接对比目标值
binarysearch (\x -> compare x 100) 1 1000 == 100  -- 结果为True

-- 示例2：查找满足x²=900的x，比较函数对比x²和900
binarysearch (\x -> compare (x * x) 900) 10 1000 == 30  -- 结果为True

注意事项与扩展 #

• 存在性假设：这个实现默认搜索区间内一定存在让比较函数返回EQ的值，且输入的起始/终止值满足f low == LT、f high == GT。如果没有这样的值，函数会无限递归，实际使用中可以修改为返回Maybe a来处理不存在的情况，比如：

  binarysearch :: Integral a => (a -> Ordering) -> a -> a -> Maybe a
  binarysearch f low high
      | low > high = Nothing  -- 区间无效，返回空
      | otherwise = case f mid of
          EQ -> Just mid
          LT -> binarysearch f mid high
          GT -> binarysearch f low mid
    where
      mid = midpoint low high
  

• 支持非整数类型：如果要处理浮点数等非整数类型，需要考虑精度问题，不能无限递归，我们可以添加一个精度阈值：

  binarysearch :: Fractional a => (a -> Ordering) -> a -> a -> Maybe a
  binarysearch f low high
      | high - low < eps = if f low == EQ then Just low else Nothing
      | otherwise = case f mid of
          EQ -> Just mid
          LT -> binarysearch f mid high
          GT -> binarysearch f low mid
    where
      mid = (low + high) / 2
      eps = 1e-9  -- 自定义精度阈值
  

内容的提问来源于stack exchange，提问作者Leo Zhang