如何在Haskell中实现二进制搜索算法

二分搜索算法（Binary Search）是一种常见的算法，用于在有序列表中查找指定元素的位置。在Haskell中实现二分搜索算法可以通过递归或循环来实现。下面我将分别给出递归和循环的实现，并附上示例代码。

递归实现：

递归实现二分搜索算法的关键是定义一个辅助函数来执行真正的搜索。该函数接收一个有序列表、查找的目标元素以及列表的起始和终止索引作为参数。算法首先判断起始索引是否大于终止索引，如果是，则查找失败，返回-1。否则，计算列表的中间索引，然后判断中间元素是否等于目标元素。如果等于，则找到了目标元素，返回中间索引。如果目标元素小于中间元素，则递归调用辅助函数来在前半部分查找。如果目标元素大于中间元素，则递归调用辅助函数来在后半部分查找。

以下是使用递归实现二分搜索算法的Haskell代码：

binarySearch :: (Ord a) => [a] -> a -> Int
binarySearch xs target = search xs target 0 (length xs - 1)
  where search :: (Ord a) => [a] -> a -> Int -> Int -> Int
        search xs target start end
          | start > end = -1
          | xs !! mid == target = mid
          | xs !! mid < target = search xs target (mid + 1) end
          | otherwise = search xs target start (mid - 1)
          where mid = (start + end) div 2

使用示例：

main :: IO ()
main = do
  let xs = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
  putStrLn $ show $ binarySearch xs 8
  -- 输出：Just 3
  putStrLn $ show $ binarySearch xs 9
  -- 输出：Just -1

循环实现：

循环实现二分搜索算法的关键是使用一个循环来替代递归调用。算法首先定义一个起始索引和一个终止索引，然后进入循环。在每次循环中，算法计算列表的中间索引并比较中间元素和目标元素。如果等于，则找到了目标元素，返回中间索引。如果目标元素小于中间元素，则将终止索引更新为中间索引减1。如果目标元素大于中间元素，则将起始索引更新为中间索引加1。循环直到起始索引大于终止索引时结束，查找失败，返回-1。

以下是使用循环实现二分搜索算法的Haskell代码：

binarySearch :: (Ord a) => [a] -> a -> Int
binarySearch xs target = search xs target 0 (length xs - 1)
  where search :: (Ord a) => [a] -> a -> Int -> Int -> Int
        search xs target start end
          | start > end = -1
          | otherwise = loop start end
          where loop start end
                  | start > end = -1
                  | xs !! mid == target = mid
                  | xs !! mid < target = loop (mid + 1) end
                  | otherwise = loop start (mid - 1)
                  where mid = (start + end) div 2

使用示例与递归实现相同。

通过以上方法，我们可以在Haskell中实现二分搜索算法。递归和循环实现都具有相似的时间复杂度，都为O(log n)，其中n为列表的长度。这使得二分搜索算法成为高效的查找算法之一。