二分搜索.txt

个人笔记 适合初学者 josephus小孩围圈问题 二分搜索 活动安排问题

template<class T>
int binarysearch(T a[],const T& x,int n)
{//在a[0]<=a[1]<=...<=a[n-1]中搜索x
//找到x时返回其在数组中的位置，否则返回-1
int left=0;int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if(x==a[middle]) return middle;
if(x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;    //未找到x
}