Chinaunix首页 | 论坛 | 博客
  • 博客访问: 862315
  • 博文数量: 581
  • 博客积分: 7803
  • 博客等级: 少将
  • 技术积分: 3653
  • 用 户 组: 普通用户
  • 注册时间: 2007-04-27 08:21
文章分类

全部博文(581)

文章存档

2013年(7)

2012年(414)

2011年(159)

2009年(1)

分类:

2012-01-19 13:17:25

作者:gfree.wind@gmail.com
博客:blog.focus-linux.net   linuxfocus.blog.chinaunix.net
 
 
本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
======================================================================================================
前一篇文章中使用haskell实现了快速排序——这个非常符合haskell的特性。下面来看看经典算法二分查找的haskell实现。

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

我使用两种方式实现了二分查找
  1. binary_search1' obj [] len = False
  2. binary_search1' obj (x:[]) len = (x == obj)
  3. binary_search1' obj xs len
  4.       | m_value == obj = True
  5.       | m_value > obj = binary_search1' obj (take middle xs) middle
  6.       | m_value < obj = binary_search1' obj (drop (middle+1) xs) (len-middle-1)
  7.       where middle = (len-1) `div` 2
  8.             m_value = xs!!middle

  9. binary_search1 obj xs = binary_search1' obj xs (length xs)
这种方式将已有列表缩短为原来的一半。以C语言的感觉,貌似效率低。但是我感觉haskell不会使用复制的方法来生成新的列表。
简单解释一下,仍然利用haskell函数的pattern match
1. 空列表,返回false
2. 只有一个元素,返回与该元素比较的结果
3. 与中间元素相比较:
    a)如果相等,返回true
    b)  如果中间元素大于目标,那么继续检查中间元素前面的列表
    c)如果中间元素小于目标,那么继续检查中间元素后面的列表


再看另一种方式:
  1. binary_search2' obj [] left right = False
  2. binary_search2' obj xs left right
  3.     | left > right = False
  4.     | m_value == obj = True
  5.     | m_value > obj = binary_search2' obj xs 0 (middle-1)
  6.     | m_value < obj = binary_search2' obj xs (middle+1) right
  7.     where middle = (left+right) `div` 2
  8.           m_value = xs!!middle

  9. 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的程序写起来果然有不同的感觉,思考问题的方式也与传统的编程语言不同。真的有点意思哦。

阅读(429) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~