关于Haskell二分搜索函数bsearch的功能与执行逻辑咨询

首先先把函数定义放出来，方便咱们对照看：

bsearch :: Ord a => [a] -> a -> Bool
bsearch [] _ = False
bsearch xs x = if x < y then bsearch ys1 x
               else if x > y then bsearch ys2 x
               else True
               where ys1 = take l xs
                     (y:ys2) = drop l xs
                     l = length xs `div` 2

先理解函数的核心逻辑 #

这个函数是典型的二分搜索实现，但有个关键前提：传入的列表必须是已经排序好的（因为用了Ord类型约束，且二分逻辑本身就需要有序列表才能有效缩小搜索范围）。它的工作思路很清晰：

• 空列表直接返回False：空列表里肯定找不到目标元素
• 非空列表时：
  1. 先计算列表长度的一半l（用整数除法div取整）
  2. 用take l xs把列表前半部分切出来存在ys1里
  3. 用drop l xs切掉前l个元素，剩下的部分第一个元素是中间值y，剩下的尾部存在ys2里
  4. 对比目标x和中间值y：
     • 如果x < y，说明目标可能在前半部分，递归搜索ys1
     • 如果x > y，说明目标可能在后半部分，递归搜索ys2
     • 如果两者相等，说明找到了，直接返回True

你的示例执行流程验证：bsearch [1,2,3,4] 4 #

咱们一步一步展开每一次递归调用，你就能看清楚整个过程了：

第一次调用：bsearch [1,2,3,4] 4 #

• 当前xs = [1,2,3,4]，目标x=4
• 计算l = length [1,2,3,4] div2 = 4div 2 = 2
• ys1 = take 2 [1,2,3,4] = [1,2]
• drop 2 [1,2,3,4] = [3,4]，通过模式匹配(y:ys2)得到y=3，ys2=[4]
• 对比4和3：4 > 3为真，所以递归调用bsearch [4] 4

第二次调用：bsearch [4] 4 #

• 当前xs = [4]，目标x=4
• 计算l = length [4] div2 = 1div 2 = 0
• ys1 = take 0 [4] = []
• drop 0 [4] = [4]，通过模式匹配(y:ys2)得到y=4，ys2=[]
• 对比4和4：4 < 4是假，4 > 4也是假，所以进入最后一个分支，返回True

你的推测完全正确！这就是这个示例的完整执行流程～

额外补充几个小细节 #

• 这个实现对奇数长度的列表也能正常工作，比如bsearch [1,2,3,4,5] 3：l=5div2=2，drop 2 xs得到[3,4,5]，y=3，直接匹配返回True
• 一定要注意：如果传入未排序的列表，这个函数会返回错误结果，比如bsearch [3,1,2] 1会错误返回False，因为二分搜索的核心逻辑完全依赖列表的有序性

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