Haskell(4)——实现二分查找

作者：[e-mail]
博客：blog.focus-linux.net   linuxfocus.blog.chinaunix.net 

 

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。

======================================================================================================

前一篇文章中使用haskell实现了快速排序——这个非常符合haskell的特性。下面来看看经典算法二分查找的haskell实现。

注：第一个参数为要查找的目标，第二个参数为排序好的列表。如目标值存在于列表，那么返回true，如果不存在，返回false。

我使用两种方式实现了二分查找

binary_search1' obj [] len = False
binary_search1' obj (x:[]) len = (x == obj)
binary_search1' obj xs len
      | m_value == obj = True
      | m_value > obj = binary_search1' obj (take middle xs) middle
      | m_value < obj = binary_search1' obj (drop (middle+1) xs) (len-middle-1)
      where middle = (len-1) `div` 2
            m_value = xs!!middle

binary_search1 obj xs = binary_search1' obj xs (length xs)

这种方式将已有列表缩短为原来的一半。以C语言的感觉，貌似效率低。但是我感觉haskell不会使用复制的方法来生成新的列表。

简单解释一下，仍然利用haskell函数的pattern match

1. 空列表，返回false

2. 只有一个元素，返回与该元素比较的结果

3. 与中间元素相比较：

    a）如果相等，返回true

    b)  如果中间元素大于目标，那么继续检查中间元素前面的列表

    c）如果中间元素小于目标，那么继续检查中间元素后面的列表

再看另一种方式：

binary_search2' obj [] left right = False
binary_search2' obj xs left right
    | left > right = False
    | m_value == obj = True
    | m_value > obj = binary_search2' obj xs 0 (middle-1)
    | m_value < obj = binary_search2' obj xs (middle+1) right
    where middle = (left+right) `div` 2
          m_value = xs!!middle

binary_search2 obj xs = binary_search2

这种方式与C实现更相似，没有对列表的操作，只是通过移动left和right来实现的。

简单解释一下；

1. 空列表：返回false

2. 非空列表：

a）如果left大于right，返回false

b）如果中间值等于目标，返回true

c）如果中间值大于目标，那么left不变，right变为middle-1

d）如果中间值小于目标，那么right不变，left变为middle+1

haskell的程序写起来果然有不同的感觉，思考问题的方式也与传统的编程语言不同。真的有点意思哦。