来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-search

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个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]之间。

二、二分查找

二分查找的前提要求是数组有序，一趟二分查找的算法描述为：

1. 确定数组上下边界，然后取中间值mid。

2. 对比中间值mid和目标值target，此时有两种情况：

   • 如果target小于mid，说明目标值在下边界区，继续在下半边界执行步骤1。
   • 如果target大于mid，说明目标值在上边界区，继续在上半边界执行步骤1。
3. 如果上下边界一直找完都没有找到目标值，说明数组中不存在指定数据。

图文描述

在数组[2, 3, 4, 5, 6, 7, 8]中查找3。第一步，计算mid是下标为3的值5，此时5比目标值3要大，说明3出现在5左边，要在[low, mid)进行下一步查找：

第二步，重新定位修改区域，查找的下标范围是[0, 2]。此时mid计算出来等于1，下标等于1的元素值为3，刚好就是我们要找的目标值，查找完成：

三、代码

需要注意的点已经在代码中标出：

1. 注意有符号、无符号以及数据是否会溢出。当前题目中数据不大，所以直接使用int。
2. 循环结束的条件是low > high，所以循环条件一定是low <= high，不要少了等于符号。
3. 没有找到目标值的时候，返回-1。

这么简单的一个题目，提交了4次才通过。。。。基础很重要！！！

/*
* 二分查找法法
* @nums 数组
* @target 待查找的目标元素
* @return 找到返回数组下标，没找到返回-1
*/
int search(vector<int> &nums, int target) {
    // [1] 注意数据溢出
    int low, high, mid;

    low = 0;
    high = nums.size() - 1;

    // [2] 判断条件是小于等于，而不是小于
    while (low <= high) {
        mid = (low + high) / 2;
        if (target < nums[mid]) {
            high = mid - 1;
        } else if (target > nums[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    // [3] 没找到默认返回-1
    return -1;
}