递归
int binarySearch(int a[], int low, int high, int target) {
if(low > high) //边界检查
return -1;
int middle = (low + high)/2;
if(target == a[middle])
return middle;
if(target < a[middle])
return binarySearch(a, low, middle-1, target);
if(target > a[middle])
return binarySearch(a, middle+1, high, target);
}
非递归
int binarySearch2(int a[], int low, int high, int target) {
int middle;
while(low <= high) {
middle = (low + high)/2;
if(target == a[middle])
return middle;
else if(target < a[middle])
high = middle - 1;
else
low = middle + 1;
}
return -1;
}
注意:
1,为防止溢出,mid=low + (high-low)/2
2,high=mid-1, low=mid+1, 这样才能保证遍历到区间内的每一个点。如果是最后为了保证区间长度为1,应写为:
while(high-low>1) {
mid = (low + high)/2;
if()
return ;
else if()
high = mid;
else
low = mid;
}
网友评论