二分查找

有序表

class Ordered_list:public List<Record>{
public:
	Ordered_list();
	Error_code insert(const Record &data);
	Error_code insert(int position,const Record &data);
	Error_code replace(int position,const Record &data);
};

Error_code recursive_binary_1(const Ordered_list &the_list,const Key &target,int bottom,int top,int &position)
{
	Record data;
	if(bottom<top)
		int mid=(bottom+top)/2;
	the_list.retrieve(mid,data);
	if(data<target)
		return recursive_binary_1(the_list,target,mid+1,top,position);
	else
		return recursive_binary_1(the_list,target,bottom,mid,position);
	}
	else if(top<bottom)
		return not_present;
	else {
	position=bottom;
	the_list.retrieve(bottom,data);
	if(data==target) return success;
	else return not_present;
	}
}

Error_code recursive_binary_2(const Ordered_list &the_list,const Key &target,int bottom,int top,int &position)
{
	Record data;
	if(bottom<=top){
		int mid=(bottom+top)/2;
		the_list.retrieve(mid,data);
		if(data==target){
			position=mid;
			return success;
		}
		else if (data<target)
			return recursive_binary_2(the_list,target,mid+1,top,position);
		else 
			return recursive_binary_2(the_list,target,bottom,mid,position);
	}
	else return not_present;
}