排除法

在这一节内容的一开始，我们先来看一下，「力扣」第 704 题另外两种「二分查找」的写法，事实上这两种写法在思想上是一样的。

参考代码 1：

// 「力扣」第 704 题：二分查找
const search = (nums, target) => {
    let left = 0, right = nums.length - 1;
  // 目标元素可能存在在区间 [left, right]
  while (left < right) {
    let mid = (left + right)>>>1;
    // 下一轮搜索区间是 [mid + 1, right]
    if (nums[mid] < target) left = mid + 1;
    // 下一轮搜索区间是 [left, mid]
    else right = mid; 
    }
  }
  if (nums[left] == target) return left;
  return -1;
}

参考代码 2：

// 「力扣」第 704 题：二分查找

const search = (nums, target) => {
    let left = 0, right = nums.length - 1;
  // 目标元素可能存在在区间 [left, right]
  while (left < right) {
    let mid = left + (right - left + 1) / 2; // 向上取整
    // 下一轮搜索区间是 [mid + 1, right]
    if (nums[mid] > target) right = mid - 1;
    // 下一轮搜索区间是 [left, mid]
    else left = mid; 

  }
  if (nums[left] == target) return left;
  return -1;
}

我们看一下，这两种写法和思路 1 的写法有何不同。

循环可以继续的条件是 **while (left < right)** ，这是一个很重要的标志。为什么是严格小于呢？我们上一节说过，当 **left == right** ，左边界和右边界重合的时候，区间里只有 1 个元素时候，二分查找的逻辑还需要继续下去；
而现在大家看到的这个解法在 **left == right** 重合的时候就退出了循环，这一点表示区间里只剩下一个元素的时候，有可能这个元素就是我们要找的那个元素。这一点与二分查找算法的思路 2（在循环体中排除元素）是一致的：排除了所有错误的答案，如果题目告诉我们只有 1 个目标元素，那么剩下的这个元素就一定是目标元素。

在退出循环以后，还需要单独做一次判断；那么这样的写法是不是更麻烦了呢？
其实不是的 !!!

1. 首先，有些算法问题根据题目的意思，要找的目标元素一定落在题目给的区间里，那么最后的这一步判断可以省略；

2. 并且我们看到这个写法只把区间分成了两个部分，其实在我们编写代码的时候要考虑的因素会更少。这两个区间没有交集，并且它们合起来组成了整个当前待搜索的区间。因此，在思考缩小待搜索区间的逻辑的时候，只需要考虑其中一种情况，另一种情况得到的区间就正好是上一个区间的反面区间；

3. 那么如何考虑缩小问题的区间呢？通常的思路是：先思考要找的数的性质，然后对这个性质取反，也就是：先讨论看到的中间位置的元素在什么情况下不是目标元素，采用这样的思路解决问题会容易一些；

友情提示：生活中的一些事情我们往往很清楚自己不需要什么，但是说不清楚自己真正需要什么。从中间位置的元素在什么情况下不是目标元素考虑，使得问题变得简单也是类似的事实。

例如「力扣」第 704 题，我们就是要找== target的元素。对这个性质取反，就是 != target，也就是< target 或者 > target 的时候，这两个条件选择其中一个，都可以缩小问题的区间，于是就有了上面两版代码的写法；
这里细心的朋友可能发现了：let mid = left + (right - left + 1) / 2; 有个上取整，这是必须的吗？答案是必须的，如果不加的话，这一版代码会出现死循环。这个注意事项，不用刻意去记。我们在写完一个算法的时候，通常来说都会拿示例中的测试用例去执行一下我们所写的代码，在测试的时候，就能够意识到要调整下取整成为上取整。

取中间数可能需要上取整的原因
现在我们解释为什么这里需要上取整。这个二分法的思路根据中间数的值把区间分为两个部分：

1. 一定不存在目标元素的部分
2. 可能存在目标元素的部分

根据中间元素被分到哪一边，有以下两种可能：

mid被分到左边区间
这个时候区分被分为两部分：[left, mid]与[mid + 1, right]，对应设置边界的代码为 right = mid 和 left = mid + 1

mid被分到右边区间
这个时候区分被分为两部分： [left, mid - 1] 与 [mid, right]，对应设置边界的代码为 right = mid - 1和 left = mid

注意：这种情况下，当搜索区间里只剩下两个元素的时候，一定要将取中间数的行为改成上取整，也就是在括号里加 1。

这是因为 [left, right]区间里只剩下两个元素的时候，如果是取中间数mid 是下取整，一旦进入left = mid这个分支，区间就不会再缩小，下一轮搜索的区间还是 [left, right] ，下一次循环取 mid 还是看到了 left ，由于逻辑和上一轮循环一样，因此搜索区间不会缩小，就这样一直下去，这是一个死循环。

解决方案也很简单，在最后一次循环的时候，把取中间数的时候修改为上取整。那么是不是要做一次判断，什么时候到了最后一轮循环呢？没有必要，整个循环体内，上取整就可以了。这个结论很重要，希望大家能够理解这里上取整的原因。根据循环体里，中位数被分到哪个区间，来决定取中间数的时候是否上取整。

友情提示：这一点是需要调试深刻理解的，大家在遇到死循环的时候，把变量 left 和 right 和相关变量的值做一个打印输出，就会看得非常清楚。

下面我们为大家总结「排除法」思路下二分查找的编码要点。

编码要点

1. 循环终止条件写成：while (left < right) ，表示退出循环的时候只剩下一个元素；

2. 在循环体内考虑如何缩减待搜索区间，也可以认为是在待搜索区间里排除一定不存在目标元素的区间；

3. 根据中间数被分到左边和右边区间，来调整取中间数的行为

4. 如缩小待搜索区间，一个有效的办法是：从 nums[mid] 满足什么条件的时候一定不是目标元素去考虑，进而考虑 mid 的左边元素和右边元素哪一边可能存在目标元素。一个结论是：当看到 left = mid 的时候，取中间数需要上取整，这一点是为了避免死循环；

5. 退出循环的时候，根据题意看是否需要单独判断最后剩下的那个数是不是目标元素。

边界设置的两种写法：

1. right = mid 和 left = mid + 1 和 int mid = left + (right - left) / 2; 一定是配对出现的；
2. right = mid - 1 和 left = mid 和 int mid = left + (right - left + 1) / 2; 一定是配对出现的。

这一点不需要记忆，大家只要一直思考目标元素可能存在的区间就可以了。就像我们在代码注释里展示给大家的一样。因为下一轮搜索的区间是 [left, mid] 所以这个时候设置 right = mid 。当前这条性质不满足的时候，既然整个区间是 [left, right] 区间里，第一种情况所在区间是 [left, mid] ，那么另外一种情况对应的区间是 [mid + 1, right] ，两个区间合起来就是整个区间 [left, right] 。同理，去理解 right = mid - 1 和 left = mid 这两个边界设置。

适用范围
这种二分查找的思路，对于查找边界问题，会使得思考的过程变得简单。

二分查找的思路 1，有的时候要考虑返回是 left 还是 right，在循环体内有 3 个分支，如何分类讨论，有些时候并不那么容易。

思路 2 的分支只有 2 个，其中一个思考对了，另外一个就可以直接得到。其实思路 2 更符合二分这个语义，我们就是将区间一分为二地去看待，一部分一定不存在目标元素，我们把它排除掉了，我们在另外一个可能存在目标元素的区间里继续查找。

希望大家能够通过练习体会这种思路写二分查找的细节，使用它写对所有的二分查找的问题。这个思路在维基百科上有一个非常简短的描述，那就是「将判断相等的步骤放到算法末尾，虽然将平均迭代次数增加 11 次，但是每次迭代中的比较次数减少了11 次」。我们来理解一下这个说法：

如果数组里一定存在目标元素，那么第一种思路运气好的话，可能很快就可以返回；但是在数组里一定找不到目标元素的时候，两种思路下的循环体执行的次数是一样的，这就是思路 2 比思路 1 平均迭代次数增加 11 次的意思；
但是由于循环体内部，思路 2 只将区间分为了 2 个区间，因此执行的判断语句平均来看是少了 1 次的。
各有优劣，其实又回答了我们在这个课程第 1 章节向大家介绍的，所有的算法都是交换，有得到就会有失去。希望大家能够通过这一句描述理解这两种思路的不同之处和优缺点、适用范围。

我们在这里给大家的建议是：

1. 如果这个二分查找的问题比较简单，在输入数组里不同元素的个数只有 1 个，使用思路 1 ，在循环体内查找这个元素；
2. 如果这个二分查找的问题比较复杂，要你找一个可能在数组里不存在，或者是找边界这样的问题，使用思路 2 ，在循环体内排除一定不存在目标元素的区间会更简单一些。