从LeetCode No.34谈二分查找

从LeetCode No.34谈二分查找

从LeetCode No.34说起

题目描述:

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。


示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]


示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

首先贴一下我的LeetCode运行结果,运行时间:打败100%的人

分析

一般我们看到时间复杂度是O(log n)级别的话,第一反应就是使用二分查找法。实际上二分查找是一种思想很简单,但是细节很困难的算法。

困难的地方就在于要明确分区点。我们先说说一般的二分查找

常规二分查找

Java代码:

    public int search(int[] nums, int target) {

        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
          int mid = (end + start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else if (target > nums[mid]){
                start = mid + 1;
            }
        }
        return -1;
    }

分析:

首先确定我们的查找区间是[left, right],也就是[0 , nums.length - 1], 这个时候末尾区间元素是数组nums的最后一个数字,因此为了覆盖到最后一个元素,我们的循环条件应该是 '<= ' 而不是 '<'

然后我们来看看分区点的判断条件(注意查找的数组是有序的)

  • 如果mid正好是要找数字的下标,那么直接返回,这个应该很容易理解
  • 如果mid比target要小,那么说明target在右半区间,因此要把start变大,而mid已经判断过了,因此是start = mid + 1
  • 如果mid比target要打,那么说明target在左半区间,因此要把end变小,而mid已经判断过了,因此是end = mid - 1

最后我们来分析一下结束循环的几种情况

  • 目标处于数组中,通过不断修改mid,最终一定是可以找到对应下标的,正常结束循环
  • 目标比数组中所有数字都要小,例如:[1,2,3,4,5], target = 0, 这个时候不断缩小end,从左半区间中查找,直到最后mid = 0,end = mid - 1 = -1, 不满足 start <= end 结束循环。
  • 目标比数组中所有数字都要打,例如:[1,2,3,4,5], target= 6, 这个时候不断增大start,从右半区间中查找,直到最后mid = 4(因为我们下标区间就是[0, 4]),start = mid + 1 = 5, 不满足条件,结束循环

可以看到,在常规的二分查找中,分区点是很明确的,因为每个元素都只会判断一次,不符合就不用再去管它了。

这个时候我们再来思考一个问题:如果我要找的元素不是唯一的,而我想要找到第一个出现这个元素的位置,该怎么办呢?

举个例子:target = 2,nums = [1,2,2,3,3]

我们想要得到的结果是1,因为第一个2出现的下标就是1,但是如果用上面的算法,在第一次循环中就会直接返回2了,我们该怎么修改一下,使得他能够返回我们要的答案呢?

二分查找变形 - 第一个元素位置

我们先直接贴代码,然后再来分析为什么要这么写

Java代码:

   private int leftBound(int[] nums, int target) {
        if (nums == null || nums.length == 0 ) return -1;

        int left = 0;
        int right = nums.length - 1;  // 确定右区间

        // 确定边界条件
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        if (left == nums.length || nums [left] != target) return -1;

        return left;
    }

分析:

首先要注意的是,我们这里的右区间是nums.length - 1,也就是数组的最后一个元素,通过上面常规算法的分析,我们知道了结束循环的条件是 <= ,因为如果是 < 的话,万一target正好是最后一个,那就永远无法找到了

理解了这个前置条件之后,我们再来看看分区点是如何被改变的,上面说到,如果按照常规的算法,那么在第一次找到target的时候就会返回结果,为了解决这个问题,我们在第一次找到的时候不返回,而是找到最后确定左边没有target元素了,再返回,这样就可以了。

这个算法的查找过程:

  • 如果mid = target,继续从左半区间查找target,看看有没有相同的值,把right修改为 mid - 1
  • 如果不等,target比mid大就从右半边找,target比mid就从左半边找
  • 最终返回的值区间为[-1, nums.length - 1]

这里重点分析一下几种特殊情况:

nums = [2,2,2,2,2] target = 2,不断修改mid,最终mid = 0,right = -1,结束循环,left = 0

nums = [2,2,2,2,3] target = 3,不断修改mid,最终mid = 4,right = 3,结束循环,left = 4

nums = [1,2,3,4,5] target = 0,注意:这种情况下虽然left是0,但是实际上nums[0]并不是我们要找的target,因此要在函数的最后加上一个判断:nums[left] == target

nums = [1,2,3,4,5] target = 6, 注意:这种情况下left = 5,因此加上判断 left = nums.length,否则会出现数组越界的错误。

二分查找变形 - 最后一个元素位置

这种情况和上面的情况类似,我们就直接贴代码吧

Java代码:

private int rightBound(int[] nums, int target) {
        if (nums == null || nums.length == 0 ) return -1;

        int left = 0;
        int right = nums.length - 1;

        // 确定边界条件
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        if (right == -1 || nums[right] != target) return -1;

        return right;
    }

分析:

这里的情况和上面的变形类似,不过有个地方需要注意,就是在最后加的判断条件

如果:

nums = [1,2,3,4,5] target = 0, 这个时候right = -1 结束循环,因此我们判断要写 - 1,而不是 0

nums = [1,2,3,4,5] target = 6, 这个时候 right = 4 循环结束,但是nums[4] 不是我们要找的。因此要加上判断

LeetCode No.34解答

结合上面所说的两种情况,在这里我们就可以通过两次二分查找,分别找到第一个和最后一个元素的位置了。

Java代码:

public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = leftBound(nums, target);
        result[1] = rightBound(nums, target);

        return result;
    }

     private int leftBound(int[] nums, int target) {
        if (nums == null || nums.length == 0 ) return -1;

        int left = 0;
        int right = nums.length - 1;

        // 确定边界条件
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        if (left == nums.length || nums [left] != target) return -1;

        return left;
    }

    // 寻找最后一个出现的下标(最大右边界)
    private int rightBound(int[] nums, int target) {
        if (nums == null || nums.length == 0 ) return -1;

        int left = 0;
        int right = nums.length - 1;

        // 确定边界条件
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        if (right == -1 || nums[right] != target) return -1;

        return right;
    }

总结

我们通过LeetCode第34题来分析了一下二分查找和二分查找的变形。除了LeetCode的34题,还有33题也是属于二分的变形题。大家有兴趣可以去看看。

二分查找的主要难点就是在于如何划分分区点,避免数组越界和查找不到的问题。想要熟练掌握二分查找,只能通过多做题多总结,在做题的过程中可以自己试一下这些特殊的数组,看看自己设定的查找分区和分区点条件是否有问题,然后再进行调整。

感谢大家的阅读,也希望大家多沟通交流,写的不够好的地方欢迎批评指正~

2 thoughts on “从LeetCode No.34谈二分查找

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注