折半查找又称二分查找，只能适用于有序的顺序表。

//折半查找
int Bsearch(int R[],int low,int high,int key){
	int min;
	while(low<=high){
		mid=(low+high)/2;	//取中间位置
		if(R[mid]==key)	//查找成功
			return mid;
		else if(R[mid]>key)
			high=mid-1;	//从前半部分继续查找 
		else
			low=mid+1;	//从后半部分继续查找 
	}
	return -1;	//查找失败 
}

折半查找的过程可用二叉树来描述，称为判定树。圆形结点表示数组中存在的元素，矩形叶结点表示查找失败的元素。

等概率查找时，n个元素查找成功的ASL（平均查找长度）=log(n+1)，log(n+1)应向上取整，但是那个符号敲不出来。。。