这个二进制搜索功能到底是什么？

Question

我很难理解这个二进制搜索函数是如何工作的：

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

我试着用一个例子来思考：bsearch [1,2,3,4] 4 但我不明白函数从哪里开始。我喜欢相信首先 l = length xs 'div' 2 得到计算。 l = 2是结果。现在我把我的变量放在 (y:ys2) = drop l xs where (y:ys2) = 3:[4] 等于 drop 2 [1,2,3,4] = [3,4]。接下来 else if 4 > 3 then bsearch ys2 x 在 ys2 = [4] 和 x = 4 处执行。接下来发生什么？ x = 4和ys2 = [4]如何比较？

编辑：我认为因为 bsearch [4] 4 是新的 bsearch xs x 执行 drop 0 [4] = [4] = (4:[]) 的新的 l = length xs 'div' 2 = length [4] 'div' 2 = 0。 4 < 4 和 4 > 4 是 False 因此 else True。这是我的示例中此函数的执行方式吗？

如果有人能帮助我实现这个功能，我将非常高兴。

Answer 1

您对绑定扩展方式的解释是正确的。该函数本质上是通过按需将有限排序列表转换为二叉搜索树来运行的。我可以重写部分函数只是为了显示树结构（请注意 where 部分未更改）：

data Tree a = Node (Tree a) a (Tree a) | Empty
  deriving Show

tree [] = Empty
tree xs = Node (tree ys1) y (tree ys2)
  where
    ys1 = take l xs
    (y:ys2) = drop l xs
    l = length xs `div` 2

然后可以生成树形：

*Main> tree [1..4]
Node (Node (Node Empty 1 Empty) 2 Empty) 3 (Node Empty 4 Empty)

递归的上半部分是关于只遍历树的相关部分。

bsearchT Empty _ = False
bsearchT (Node ys1 y ys2) x =
   if      x < y then bsearchT ys1 x
   else if x > y then bsearchT ys2 x
   else               True

bsearch xs x = bsearchT (tree xs) x

操作本身确实表明普通列表不是合适的数据类型；我们可以观察到 Data.List.Ordered.member performs a linear search, because lists must be traversed from the head and may be infinite. Arrays or vectors provide random access, so there is indeed a Data.Vector.Algorithms.Search.binarySearch。

这个二进制搜索功能到底是什么？

What does this binary-search function exactly?

haskell

list

binary-search