同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


二分查找

  • 时间:2022-05-08
  • 题目序号:704
  • 难度:简单

问题描述:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

来源:力扣(LeetCode)

示例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. 设置三个变量来分别指向数组的左(left)中(middle)右(right)三个位置
  2. 二分查找就是将数组分为两个部分,每次将中间的值(middle)与目标值(target)进行比对(前提是数组内的数据必须有序,这里默认升序来做讲解,降序也是类似的思想)

    • 如果middle大于target,则说明需要查找的值在middle左半边(right = middle - 1)
    • 如果middle小于target,则说明需要查找的值在middle右半边(left = middle + 1)
  3. 通过不断地缩小范围进行比对,最终查找出目标值的索引(查不到为-1)
这里需要注意的就是三个指针变量的临界值判断

代码实现

通过上述分析,分别可以通过循环和递归两种方式来实现二分查找

循环

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int middle = left + ((right - left) >> 1);
            if(nums[middle] == target) return middle;
            else if(nums[middle] > target) right = middle - 1;
            else left = middle + 1;
        }
        return -1;        // 未找到,返回-1
    }
}

注意

上方代码中middle = left + ((right - left) >> 1)是为了防止数据溢出

如果left + right 值超过了int类型能存储的最大值,middle = (left + right) / 2就会报错

>>1等价于/2,但是位运算是直接对二进制数据做运算,效率更高

递归

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }
    public int binarySearch(int[] nums, int target, int left, int right){
        if(left > right) return -1;
        int middle = left + ((right - left) >> 1);
        if(nums[middle] == target) return middle;
        else if(nums[middle] > target) return binarySearch(nums, target, left, middle - 1);
        else return binarySearch(nums, target, middle + 1, right);
    }
}


总结

  • 二分查找必要条件是数组中的元素有序,而且不能重复(如果有重复值,查到的索引可能就有问题)
  • 一定要注意循环以及递归的判断条件(临界值)
  • 尽可能抓住每一个可以优化的地方,从小到大(溢出问题、位运算代替除运算等)
最后修改:2022 年 05 月 12 日
如果觉得我的文章对你有用,请随意赞赏