菜鸟天堂

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

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

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

     摘要: 实现一个最简单的顺序查找算法，如下所示：
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个失败节点。
  阅读全文