2006年8月30日

     摘要: 本文是《数据结构与程序设计(c++语言描述)》中关于二分搜索的学习笔记,二分搜索的思想很简单,但是要实现一个正确最优的算法确不是那么容易。第一个二分搜索算法于1946年就出现,然而第一个完全正确的二分搜索算法直到1962年才出现,所以,认真点+留神点~ ^_^

首先,介绍一下二分搜索的思想:对于一个有序表而言,要查找某个关键字,首先比较表中央的那个节点,如果该节点的关键字与目标关键字相同,则找到。若比目标小,则目标关键字肯定出现在该点的右半段内。反之则出现在左半段。这样,每次比较后就能丢去一半的节点,对于一般的有序线性表而言,其搜索效率大大高于顺序查找。

第一个版本的二分搜索:
根据算法,我们设置三个位置指示器:low, high, mid,分别指向当前搜索范围的最低位置、最高位置和中间位置,中间位置由mid = (low+high)/2决定。首先将mid处的关键字与key比较,相同则返回mid;若key较大,令low=mid+1继续搜索右半段;若key较小,令high=mid-1继续搜索左半段。这样,搜索范围不断减小,high-low也越来  阅读全文

posted @ 2006-08-30 23:24 樱木 阅读(2256) | 评论 (1)编辑 收藏

     摘要: 实现一个最简单的顺序查找算法,如下所示:
template
int sequential_search( Record *r, const int & size, const Key & k )
{
for(int i=0; i if( r[i] == k )
return i;
return -1;
}
有几点需要注意的:
1)如果在数组的最低或最高单元加上一个哨兵元素(sentinel),则可以在每次迭代中少一个判断(i2)在仅考虑搜索成功以及等概率搜索的前提下,顺序查找的的关键字比较次数为n*(n+1)/2。
3)常见搜索算法的时间复杂度是以关键字比较的次数来进行度量的。
4)与二分搜索不同,顺序搜索可以针对无序表进行。
5)顺序查找的搜索树是一颗单链树,有n+1个叶子节点,其中n个成功节点,1个失败节点。
  阅读全文

posted @ 2006-08-30 16:03 樱木 阅读(206) | 评论 (0)编辑 收藏