二分法中间区间的定义一般有两种，一种是左闭右闭即[left, right],另一种是左闭右开即[left, right)。区间的定义决定了应该如何写二分法的代码！

二分写法一：

• [left, right]： 此时left与right相等的情况是有意义的，所以while(left <= right)中要使用"<="

• 如果nums[middle] 大于 target,则更新搜索范围的右下标right为middle - 1.因为当前这个nums[middle]一定不是target，所以接下来要查找的左区间结束下标位置是middle - 1.

//leetCode. 704
class Solution {
public: 
	int search(vector& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
    int mid = (left + right) / 2;
    if (nums[mid] > target) {
		right = mid - 1;//target在左区间[left, mid - 1];
     } else if (nums[mid] < target) {
       		left = middle + 1;//target在右区间[mid + 1, right];
     } else {
       		return mid;
     }
   }
   return -1;
 }
}

二分写法二：

• [left, right)： 此时left与right相等的情况是没有意义的，所以while(left < right)中要使用"<"。

• 如果nums[middle] 大于 target,则更新搜索范围的右下标right为middle .因为当前这个nums[middle]不等于target，那么去左区间继续寻找，而寻找的区间是左闭右开区间，所以right更新为middle,即在下一个查询区间不会比较nums[middle]。

//leetCode. 704
class Solution {
public: 
	int search(vector& nums, int target) {
    int left = 0;
    int right = nums.size();//[left, right);
    while (left < right) {
    int mid = (left + right) / 2;
    if (nums[mid] > target) {
		right = mid;//target在左区间[left, mid);
     } else if (nums[mid] < target) {
       		left = middle + 1;//target在右区间[mid + 1, right);
     } else {
       		return mid;
     }
   }
   return -1;
 }
}

Tip:常见的int mid = left + (right - left) / 2 写法，是为了防止数值越界。

再谈二分法

• 二分的本质是二段性，而非单调性。

LC.162. 寻找峰值

class Solution {
    public int findPeakElement (int [] nums) {
    	//爬山一定会遇到波峰，向着升高的方向搜寻
        //nums[-1] = -∞， nums[n] = -∞
    	int left = 0, right = nums.length-1;
        while(left < right) {
        	int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid+1]) {
            	right = mid;
            } else {
            	left = mid + 1;
            }
        }
        return right;
    }
}

• 最早在 33. 搜索旋转排序数组 中，我们强调，二分的本质是 「二段性」 而非「单调性」，而经过本题，我们进一步发现「二段性」还能继续细分，不仅仅只有满足 01 特性（满足/不满足）的「二段性」可以使用二分，满足 1? 特性（一定满足/不一定满足）也可以二分。

二分法查找只有一个思想：逐步缩小搜索区间。（颠覆了之前的认知）

链接