二分法的模板写法：

（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)左端点值（左边界）

利用二分法寻找左边界是二分查找的一个变体，应用它的题目常常有以下几种特性之一：

1. 数组有序，但包含重复元素

2. 数组部分有序，且不包含重复元素

3. 数组部分有序，且包含重复元素

既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了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;  }

(adsbygoogle = window.adsbygoogle || []).push({});