来源:力扣(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;
}

最后修改:2020 年 02 月 09 日
喜欢就给我点赞吧