【二分与分治】中间值、边界值、循环条件、模块写法(2)
二分法的模板写法：
（1）标准的二分查找（寻找的值正好等于x的任意位置）
int search(int A[], int n, int target)
{
int left = 0, right = n-1;
while(left <= right)
{
// 注意：若使用(low+high)/2求中间位置容易溢出
int mid = left+((right-left)>>1);
if(A[mid] == target)
return mid;
else if(A[mid] < target)
left = mid+1;
else // A[mid] > target
right = mid-1;
}循环条件：
left <= right中间位置计算：
mid = left + ((right -left) >> 1)左边界更新：
left = mid + 1右边界更新：
right = mid - 1返回值：
mid / -1
例如下面这题：
【题目描述】
给定一个非负整数x，计算并返回x的平方根。因为返回类型是整数，所以小数位数被截断，并且只返回结果的整数部分。
int mySqrt(int x) { if (x <= 1) return x; int left = 1; int right = x - 1;
while (left <= right) { int mid = left + ((right - left) >> 1); if (mid > x / mid) { right = mid - 1;
} else if (mid < x / mid) { if (mid + 1 > x / (mid + 1)) return mid; left = mid + 1;
} else {
return mid;
}
}
return -1; // only for return a value
}(2)左端点值（左边界）
利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：
数组有序，但包含重复元素
数组部分有序，且不包含重复元素
数组部分有序，且包含重复元素
既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界，我们还是要向左侧查找，所以我们在nums[mid]偏大或者nums[mid]就等于目标值的时候，继续收缩右边界，算法模板如下：
int search(int A[], int n, int target) {
int left = 0, right = n-1;
while(left < right) {
int mid = left+(right-left)/2;
if(A[mid] < target)
left =mid+1;
else
right = mid;
}
return right;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
