题目一 ：二分查找和 278. 第一个错误的版本

注意边界的变化方式。一般是
high = mid + 1
但有的时候可能没有 +1，甚至有 -1.

题目二：35. 搜索插入位置

二分法难点就在于开闭的决定。这题就把我难住了，主要是不知道 mid 是否 + 1。

先看看别人的

有个参考

以这道题目来举例，以下的代码中定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要）。
这就决定了这个二分法的代码如何去写，大家看如下代码：
大家要仔细看注释，思考为什么要写while(left <= right)， 为什么要写right = middle - 1。

class Solution {
public:int searchInsert(vector& nums, int target) {int n = nums.size();int left = 0;int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，区间[left, right]依然有效int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle;}}// 分别处理如下四种情况// 目标值在数组所有元素之前  [0, -1]// 目标值等于数组中某一个元素  return middle;// 目标值插入数组中的位置 [left, right]，return  right + 1// 目标值在数组所有元素之后的情况 [left, right]，这是右闭区间，所以  return right + 1return right + 1;}
};

这是别人的代码，但是有个问题，他定义了“target在左闭右闭的区间里，[left, right]”，那你为什么最后返回的是“right + 1”？

再想想自己的

本质上是维护一个范围（当然还有数在范围之外的情况，另外讨论就好），关键是范围的正确缩小：就是你要插入的位置一定要在这个范围之内，所以当你调整范围的时候要慎重，别把正确的序号给排除了就好。
大概有这几种情况：

1. 如果你摸到的数就是插入的数，那这个被摸到的数的序号就是结果；
2. 如果你摸到的数小于目标，那么新来的数就不可能在 “这个数以及这个数之前了”，即 low = mid + 1（或者说新来的数不可能撼动这个较的小数的位置，只能往后排）；
3. 如果你摸到的数大于目标，新来的“小子”是可以占用你的序号的！所以 high = mid（没有 -1）；

然后你再加上“数在范围之外的情况”，应该就好了。代码如下

    int searchInsert(vector& nums, int target) {int  low = 0, high = nums.size() - 1;// 数在范围之外的情况if (target <= nums[low]) return 0;if (target > nums[high]) return high+1;while (low < high){//if (high - low == 1) return high;int mid = low + (high - low) / 2;if (nums[mid] > target) high = mid ;if (nums[mid] < target) low = mid + 1;if (nums[mid] == target) return mid;}return high ;}

在掌握了范围的正确缩小算法后，我们再来看看前面的题目。

对于题目 704. 二分查找

套用上面的思想，可以得到：

1. 如果你摸到的数就是查找的数，直接返回；
2. 如果你摸到的数小于目标，那么新来的数一定在这个数的后面，所以用 low = mid + 1；（这有个疑问，如果你用 low = mid 的话相当于放宽了下限，但整体范围也是会缩小的，也能起到作用。不这样做的原因是好像有一次我这么干了，但巧了当时 low = mid，导致了无限循环，所以缩小范围还是不能多也不能少）
3. 如果你摸到的数大于目标，那么新来的数一定在这个数的前面！所以 high = mid - 1；

对于题目 35. 搜索插入位置

套用上面的思想，可以得到：

1. 如果你摸到的是ok，则结果绝对不会在此之后，可能是这个，也可能是这个前的，所以用 high = mid；
2. 如果是false，则结果绝对在此之后，不可能是这个，所以用 low = mid + 1。

当二分法的思路清晰之后，代码就变得简洁了（从下面的代码一 -> 代码二）

// 代码一，罗里吧嗦，奇技淫巧，一通操作
int firstBadVersion1(int n) {if (n == 1) return 1;int low = 1, high = high = n;while (low < high){int mid = low + (high - low) / 2;if (isBadVersion(mid) == true){if (isBadVersion(mid - 1) == true){high = mid - 1;mid = low + (high - low) / 2;}else return mid;}else{if (isBadVersion(mid + 1) == true) return mid + 1;else{low = mid + 1;mid = low + (high - low) / 2;}}}return low;
}
// 代码二（简洁版）
int firstBadVersion3(int n) {if (n == 1) return 1;int low = 1, high = high = n;while (low < high){int mid = low + (high - low) / 2;if (isBadVersion(mid) == true) high = mid;//如果是ok，绝对不会在此之后，可能是这个，也可能是这个前的if (isBadVersion(mid) == false) low = mid + 1;}return low;
}

完工！