二分法的模板写法：

（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;
}