折半查找算法

1.在递增有序的表中，写出折半查找的递归算法。初始调用时，low=1,high=ST.lengh。

思想：先判断是否为表空；然后进行划分左右子表，判断要找的是比中间值大还是小，对应递归左或者右表。

代码：

typedef struct{
	EleType *elem;
	int length
}SSTable; 
int BinSearch(SSTable ST,int key,int low,int high){
	if(low>high) return -1;//表空 
	int mid=(low+high)/2;//取中间位置
	if(key>SSTable.elem[mid]){
		return BinSearch(ST,key,mid+1,high);//比中间位置大，右边 
	} else if (key<SSTable.elem[mid]){
		return BinSearch(ST,key,low,mid-1);//比中间位置小，左边 
	}else{
		return mid;//找到了 
	}
} 

时间复杂度O（logn)；空间复杂度O（1） 

2.写一个非递归算法，该算法在按照值严格递增排序的顺序表A[1....n]中采用折半查找不小于item的最小元素。若存在这样的元素，则算法给出该最小元素中的位置，否则给出信息为0。

思想：

表中元素小于2时，结束查找。当前元素大于等于待查找元素时，都去左表找，否则都去右表找。

如果找到了item，则item右侧元素为不小于item的最小元素。否则查找失败

例子：

待查找表：5 10 15 20 25；带差找元素：7。返回high=2，元素为10。

代码：

typedef struct{
	EleType *elem;
	int length
}SSTable; 
int BinSearch(SSTable s,int key){
	int low=0,high=s.length;
	while(high-low>1){
		int mid=(low+high)/2;
		if(s.elem[mid]>=key){
			high=mid;
		}else{
			low=mid;
		}
	}
	return (s.elem[high]>=key)?high:0;
} 

时间复杂度O（logn)；空间复杂度O（1）