开头不空格，讲究。

原题

题目地址： https://leetcode.cn/problems/binary-search

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

---

解析思考

这是一道经典的二分查找题。

那么，什么是二分查找呢？为什么看到这道题就会想到二分查找呢？当然题目已经告诉你了这是二分查找，但是假如没有题目的提示，我们可以通过观察题干想到使用二分查找吗？我们先从什么是二分查找来切入。

经过多方的资料探究，二分查找就是：

二分查找是一种在有序数据中查找目标值的高效方法。它的基本思想是：每次都从当前范围的中间元素开始比较，根据目标值与中间值的大小关系，将查找范围缩小为原来的一半，直到找到目标或范围为空为止。由于每次都能排除一半数据，它的查找效率非常高，时间复杂度是 \( log(n) \)。

繁杂的定义总是让人头疼。那么我们用一个小例子来说明。

举个例子：

想象你在翻一本书，目标是找到第 53 页。如果你从第一页开始一页一页翻，那是最笨的方法。但你也可以每次翻到中间，看当前页是大还是小，然后判断往哪一半翻。比如第一次翻到第 100 页，太大了，目标在前面；下一次翻到第 50 页，接近了，再继续缩小范围。每次都把范围减半，这就是典型的二分查找策略。

就拿这个例子来说，找到第 53 页确实是最暴力直接的方法，但是无疑没有后面的方法快。
因为后面这种“每次折半缩小范围”的策略，大大减少了无谓的翻页次数。不管你要找的是第 53 页还是第 503 页，它都能以极快的速度接近目标。这种方式，正是二分查找的精髓所在：利用数据的有序性，快速排除一半无效区域，从而高效定位答案。

当你面对的是成千上万条数据时，线性查找可能要花几千次，而二分查找往往只需要十几次甚至更少——这就是算法的魅力。别小看这个“翻书找页码”的例子，它其实就是二分查找在生活中的一个缩影。

二分查找是万能的嘛？二分查找有局限性嘛？

那么二分查找可以运用在任何需要查找的地方吗？很显然并不能！为什么呢，因为二分查找的基础就是建立在查找的集合元素之间是有序的。

如果待查找的集合不是有序的，你如何判断该往左半边继续查找，还是往右半边？
答案是——你无法判断。因为元素的顺序是杂乱的，你根本无法凭借“中间值”和目标值的大小关系来缩小范围，这时候再用二分查找，就像在一团乱麻中盲目剪断一根线，没有意义。

所以二分查找并不是万能的，它的前提条件非常明确——集合必须是有序的。
一旦顺序被打乱，就只能退而求其次，使用线性查找这样的“全覆盖”方法了，效率也自然大打折扣。

通过上面的例子我们明白了二分查找就是在每一次查找都会缩短一半的无效区域。那么代码是如何实现的呢？

代码实现

实现思路

首先我们需要两个指针指向区域的左右位置，比如定义 left 代表待查找区间的起始位置，right 代表待查找区间的结束位置。

举个例子：

一个有序集合nums[1, 2, 3, 4, 5]，我们定义 left 为 0，因为元素 1 的索引就是 0。
同理，我们定义 right 为 5。
（这里有两种情况，right 节点的取值可以为集合的末尾索引，即 4，表示左闭右闭区间；也可以为末尾索引 +1，即 5，表示左闭右开区间，右边取不到）

那么我们这里就取左闭右开 的情况。也就是说 right 指针无法取到集合中的元素。

int left = 0; // 可以取到元素1
int left = 5; // 不可以取到元素5

那么至此我们就完成了用两个指针代表待查找集合的操作。那么如何进行查找操作呢？这里假定我们要查找的 target 为 4 。然后我们可以观察到我们待查找的集合是有序的。那么我们该如何运用二分查找的想法呢？

我们可以定一个 mid 指针，该指针就是指向待查找集合的中间位置。

那么 mid 指针的定义就为：

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

这个公式的意思是：从 left 开始，加上“当前长度的一半”，就到了中间的那个位置。

那么 nums[mid]就代表[left, right)中加的索引的元素。

我们拿这个nums[mid]和target比较，

• 如果 nums[mid] < target，说明目标数字在 mid 到 right 的区间内。那么我们就要更新 left 指针为 mid + 1（因为 mid 本身不是目标值，保留它是没意义的，排除掉它刚刚好）。
  当我们将 left 更新为 mid + 1 之后，下一轮查找的区间就变成了前一次区间的右半边。接着我们继续比较新的 left 和 right 中间的数字与 target 的大小关系，慢慢缩小查找范围，直到最终 mid 正好等于目标值所在的位置。
• 如果 nums[mid] > target，说明目标数字在 left 到 mid 之间的这一段范围内。这时候我们就要更新 right 指针为 mid。注意，这里不是 mid - 1，因为我们采用的是左闭右开区间 [left, right)，所以 right 是取不到的，而 mid 本身在这次比较中又可能就是目标值，所以不能直接丢掉它，要保留它在下一次查找中继续判断。更新 right = mid 之后，查找范围就变成了前一次区间的左半边，我们继续比较新的 mid 与目标值的大小，重复这个过程，不断缩小范围，直到最终找到了目标值为止。

假如集合中不存在该元素，查找到最后 left 和 right 就会慢慢靠近，在左闭右开 区间的情况下就是 left >= right, 因为 right 在定义之初就是无法取到的，那么取得到的 left == right 就意味着该区间是空集。

另一种情况就是 left > right 这种情况很明显区间不存在。所以程序结束返回 -1 代表所查找的数在集合中不存在。

编写代码

依据以上的思路我们可以轻松写出如下代码：

左闭右开

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

只要注意边界条件和更新条件就可以轻松写出左闭右闭的代码。

左闭右闭

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // can reach

        while(left<=right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                // update left
                left = mid + 1;
            } else {
                // update right
                right = mid - 1;
            }
        }
        return -1;
    }
};