二分查找的思想

减而治之，即将大规模问题转化成小规模问题。减而治之是分而治之的特例，将大问题划分成若干个子问题以后，最终答案只在其中一个子问题里。

二分查找的基本问题（二分查找模板一）

[LeetCode] 第704题：二分查找

代码

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

说明：

1. 循环可以继续的条件是while(left <= right)， 表示当left==right成立时，还有一个元素，即下标left(right)位置的元素还没有看到，需要继续查看这个元素的值，看看是不是目标元素；
2. 关于取中间数int mid = (left + right) / 2;在left + right很大的时候会发生整型溢出，一般这样改写：

int mid = left + (right - left) / 2;

这两种写法事实上没有太大区别，在left和right都表示数组下标的时候，几乎不会越界，因为绝大多是情况下不会开那么长的数组。

这里不建议把/2改写成>>1，理由是**高级语言在编译期间会做优化，会将2，以及除以2的方幂的操作，在内部修改为>>**，工程师只需要写程序本来的逻辑就好了。如果使用位运算，在C++中可能还需要注意运算优先级的问题。

3. 还有一个细节，/2表示的是下取整，当数组中的元素个数为偶数的时候，int mid = left + (right - left) / 2;只能取到位于左边的那个元素。取右边中间数的表达式是（其实就是在括号里+1，表示上取整）：int mid = left + (right - left) / 2;

以上代码可以认为是二分查找的模板一。

二分查找模板二（在循环体里排除不存在目标元素的区间）

说明：这个模板的难点在于理解根据分支决定取中间数是上取整还是下取整，以避免死循环。

我们上面有提到过，上取整还是下取整理应同样对待，但是在这个模板里为了避免死循环就有所区分。这一点理解清楚以后，解决二分查找问题就不会很难了。

基本思想

从考虑哪些元素一定不是目标元素开始考虑：根据看到的mid位置的元素，排除掉一定不可能存在目标元素的区间，而下一轮在可能存在目标的子区间里继续查找。

具体做法

1. 先把循环可以继续的条件携程while(left < right)，表示退出循环的时候，[left, right]这个区间里只有一个元素，这个元素有可能就是目标元素；
2. 写if和else语句时，思考当nums[mid]满足什么性质的时候，nums[mid]不是解，进而接着判断mid的左边有没有可能是解，mid的右边有没有可能是解；

理解如何避免死循环（重难点）

根据mid被分到左边区间还是右边区间，代码写出来只有以下2种：

边界收缩行为1：mid被分到左边。即区间被分成[left, mid]于[mid+1, right]，这里用[闭区间]表示区间端点可以取到，下同；

代码写出来是这样的：

if (check(mid)) {
	// 下一轮搜索区间是 [mid+1, right]
	left = mid + 1;
} else {
	right = mid;
}

边界收缩行为2：mid被分到右边。即区间被分成[left, mid - 1]与[mid, right];

if (check(mid)) {
    right = mid - 1;
}else {
	left = mid;
}

面对上面的边界收缩行为2（mid被分到右边），在待搜索区间收缩到只剩下2个元素的时候，就有可能造成死循环。搜索区间不能缩小，是造成死循环的原因。

有了上面的分析，我们把上面 [边界收缩行为] 对应的中间数取法补上：

边界收缩行为1：mid被分到左边。即区间被分成[left, mid]与[mid + 1, right]，此时取中间数的时候下取整。

int mid = left + (right - left) / 2;
if(check(mid)) {
	left = mid + 1;
} else {
	right = mid;
}

边界收缩行为2：mid被分到右边。即区间被分为[left, mid - 1]与[mid, right]，此时取中间数的时候上取整。

int mid = left + (right - left + 1) / 2;
if (check(mid)) {
	right = mid - 1;
} else {
	left = mid;
}

规则：在if else语句里面只要出现left = mid的时候，把取中间数行为改成上取整即可。