栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

入门二分查找练习题

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

入门二分查找练习题

文章目录
  • 标准的二分查找
  • 在有重复值中查找第一个出现或者最后一个出现的问题
  • 非完全有序的二分
    • 1、搜索旋转排序数组
      • 解题分析
      • 图解说明(x轴表示数组下标,y轴表示值)
      • 代码
    • 2、搜索旋转排序数组 II
      • 举例说明
      • 代码
    • 3、寻找旋转排序数组中的最小值
      • 代码实现
    • 4、寻找旋转排序数组中的最小值

标准的二分查找

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = (right - left) / 2 +left;
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return -1;
}

标准二分查找的模板:

  1. 定义指向左右下标的边界点。

  2. 不断的收拢左右下标,直到左下标越过右下标为止。

  3. 在左右下标之间找中间点,对于偶数个数组来说,(right - left) / 2 +left找到的是靠左边的位置,如果想找靠右边的位置可以写成(right - left + 1) / 2 +left。

    假设有:1,2,3,4,5,6,(right - left) / 2 +left找到mid:3,(right - left + 1) / 2 +left找到mid:4。

  4. 如果中间位置是目标值,则直接返回即可。

  5. 如果中间位置大于目标值,则表明从中间开始,其右边的数一定都大于目标值,所以把右边界指向中间位置的前一个位置,然后继续开始查找即可。

  6. 如果中间位置小于目标值,则表明从中间开始,其左边的数一定都小于目标值,所以把左边界指向中间位置的后一个位置,然后继续开始查找即可。

注意点:终止条件一定要是left<=right,而不是left

假设有:1,2,3,4,5,6,目标值为:2,则第一次查找后:left:0,mid:2,right:1,第二次查找后:left:1,mid:0,right:1,此时left==right,如果判定条件不是left<=right则会找不到目标值。

在有重复值中查找第一个出现或者最后一个出现的问题

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0){
            return new int[]{-1,-1};
        }
        int first = binarySearchTheFirst(nums, target);   
        int last = binarySearchTheLast(nums, target);   
        return new int[]{first,last};
    }

    public int binarySearchTheFirst(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = (right - left) / 2 +left;
            if(nums[mid] == target){
                // 说明mid右边的数一定大于等于mid
                // 为什么不是right = mid + 1,因为有可能右边的数大于mid,而不是等于
                right = mid;
            }else if(nums[mid] > target){
                // 说明mid右边的数一定大于mid
                right = mid - 1;
            }else{
                // nums[mid] < target 说明mid左边的数一定小于mid
                left = mid + 1;
            }
        }

        if(nums[left] != target){
            return -1;
        }

        return left;
    }

    public int binarySearchTheLast(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = (right - left + 1) / 2 +left;
            if(nums[mid] == target){
                // 说明mid左边的数一定小于等于mid
                left = mid;
            }else if(nums[mid] > target){
                // 说明mid右边的数一定大于mid
                right = mid - 1;
            }else{
                // nums[mid] < target 说明mid左边的数一定小于mid
                left = mid + 1;
            }
        }
		
        if(left > nums.length - 1 || nums[left] != target){
            return -1;
        }

        return left;
    }
}
非完全有序的二分 1、搜索旋转排序数组

来自leetcode第33题

解题分析

虽然数组不是完全有序的,但是我们不难发现,通过一次二分后,必然有一半有序的,一半无序的(但是无序的情况依旧能通过二分变为一半有序一半无序),只要符合这样的规律,那么我们就可以依然可以使用二分进行查找。

图解说明(x轴表示数组下标,y轴表示值)

假设中间点在旋转点的左边,那么中间点左半部分一定是有序的。

假设中间点在旋转点的右边,那么中间点右半部分一定是有序的。

代码
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            
            if (nums[mid] < nums[r]) {
                //如果nums[mid] < target && target <= nums[r]成立,则在mid到r的范围内找,然后在l到mid的范围找
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                //如果nums[l] <= target && target < nums[mid]成立,则在l到mid的范围内找,然后在mid到r的范围找
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
2、搜索旋转排序数组 II

来自leetcode第81题


这题与上一题不同之处在于,允许数组中有重复元素,那么也就意味有可能出现lmidr的情况,在这种情况下,我们就无法区分出哪半边是有序的。

举例说明

下面两张图,都是nums[l] = nums[mid] = nums[r] 的情况,假设目标值在升序的范围中,那么很明显两种升序的范围分别在mid左边和mid右边。

如果遇到这样的情况,我们就让l和r分别向右和向左移动一位,然后再找中间点,直到不满足 lrmid,此时我们就能判断升序到底是在mid的左边还是右边了。

代码
    public boolean search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == target) {
                return true;
            }
            //如果nums[l] == nums[mid] == nums[r],就让l、r都移动一位。其他逻辑和前一题没有重复的值情况一样
            if (nums[l] == nums[mid] && nums[r] == nums[mid]) {
                l++;
                r--;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }

            }
        }
        return false;
    }
3、寻找旋转排序数组中的最小值

这题与第一题类似,实际上也可以很容易分析出规律


从图中可以看出,当mid指向的下标值小于r指向的下标值时,则最小值一定在mid的右边,反之则一定在mid的左边。

代码实现
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            
            if (nums[r] <= nums[mid]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[r];
    }
4、寻找旋转排序数组中的最小值

结合前面几题的套路,这题就比较容易找出规律了,直接上代码,和前一题比无非就是多了一种nums[r] == nums[mid]的情况,按照套路移动一次r的下标即可。

    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[r] < nums[mid]) {
                l = mid + 1;
            } else if (nums[r] > nums[mid]) {
                r = mid;
            } else {
                r -= 1;

            }
        }
        return nums[r];
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/980826.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号