二分查找

• 时间：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);
    }
}

总结

• 二分查找必要条件是数组中的元素有序，而且不能重复（如果有重复值，查到的索引可能就有问题）
• 一定要注意循环以及递归的判断条件（临界值）
• 尽可能抓住每一个可以优化的地方，从小到大（溢出问题、位运算代替除运算等）