顺序查找算法的思路很简单：从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果到最后一个元素仍没有目标元素，则查找失败。

4.按题目要求编写最后的输出函数。

【相关代码】

二分查找算法

int sequential_search(const List<int> &the_list,
					  const Key &target)
/*Post: If an entry in the_list is equal to target, then return the position
        of this entry. 
		Otherwise return -1 
*/
{
	int position;
	int s=the_list.size();
	for(position=0;position<s;position++){
		int data;
		the_list.retrieve(position,data);
		if(data==target){
			return position;
		}
	}
	return -1;
}

二分查找前提是表是按递增或递减顺序的规范表。此次实验中我们使用的是递增表。
二分查找从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分（表是递增排列的），反之中间元素比目标元素大，则查找表的前半部分。

【实验说明】

题目：编写一个程序，对有序表{1,2,3,4,5,6,7,8,9,10},采用二分查找关键字9的过程。要求输出：
1）原顺序表；2）查找到关键字的位置；3）进行比较的次数。
1.二分查找算法的前提是表必须是有序的，如题目中是递增方式排列的表。实现表的有序一方面是用户规范输入，另一方面我们也可以编写有序的类来方便用户的输入。
所以从List中派生类Oredered_list，重新编写函数Error_code insert（int position，const Record &data），使插入的位置不满足表的有序条件时，不能插入。
同时编写插入的重载函数 Error_code insert(const Record &data)，可以直接插入到合适的位置，方便用户输入。
2.仍使用题目1中的Key来表示目标
3.实现二分查找算法。通过书中的学习，我们直接使用添加相等判断的二分查找算法。即每次从表的中间元素开始比较，如果得到目标则返回元素所在表中位置；如果中间元素小于目标元素，则对右半部分继续二分查找；反之对前半部分表进行二分查找。若最后都没有目标元素，返回-1用以表示表中没有目标元素。

4.仍使用题目1编写的输出函数将结果输出。
/*注意这里因为Ordered_list是从List中派生而来，所以虽然print_out函数中第一个参数类型是List<int>，仍可以使用，而不用编写重载函数*/

【相关代码】

函数 binary_search

int binary_search(const Ordered_list<int> &the_list,
					const Key &target)
/*Post: If an entry in the_list is equal to target, then return the position
        of this entry. 
		Otherwise return -1 
*/
{
	int position;
	int data;
	int bottom=0,top=the_list.size()-1;
	while(bottom<=top){
		position=(bottom+top)/2;
		the_list.retrieve(position,data);
		if(data==target)
			return position;
		if(data<target)bottom=position+1;
		else top=position;
	}
	return -1;
}

【结果分析】