【Leetcode】二分法问题解析

二分法是查找算法中常用的算法，通过Leetcode刷题过程中对二分法的练习和总结。

文章目录

• • • 153. 寻找旋转排序数组中的最小值
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 154. 寻找旋转排序数组中的最小值 II
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 33. 搜索旋转排序数组
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 81. 搜索旋转排序数组 II
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 1760. 袋子里最少数目的球
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 1011. 在 D 天内送达包裹的能力
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 1482. 制作 m 束花所需的最少天数
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码
    • 4. 寻找两个正序数组的中位数
    • • 1. 题目描述
      • 2. 思路分析
      • 3. 参考代码

二分法模板：

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

主要考虑的是索引是否越界，以及查找元素索引是否正确，根据题目具体调整。

153. 寻找旋转排序数组中的最小值 1. 题目描述

leetcode链接：153. 寻找旋转排序数组中的最小值

2. 思路分析

元素升序排列，使用二分查找的方法。对内部需要注意的边界问题，逐个分析一下。

1. while (left < right)，选择使用left < right，就是最后一次循环的时候，left = mid + 1，会不会执行。如果选择left < right，最后一次循环结束，不再执行left = mid + 1，只需要return nums[left]；如果选择left <= right，最后一次还会再执行一次left = mid + 1，则需要return nums[left - 1]。
2. right = mid; 例如 {4,5,1,2,3}，如果high=mid-1，则丢失了最小值1。

为什么左右不对称？

这是循环前升序排列的数，左边的数小，右边的数大，而且我们要找的是最小值，肯定是偏向左找，所以左右不对称了。

为什么比较mid与right而不比较mid与left？

简单讲就是因为我们找最小值，要偏向左找，目标值右边的情况会比较简单，容易区分，所以比较mid与right而不比较mid与left。

那么能不能通过比较mid与left来解决问题？

能，转换思路，不直接找最小值，而是先找最大值，最大值偏右，可以通过比较mid与left来找到最大值，最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余）。

3. 参考代码

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

154. 寻找旋转排序数组中的最小值 II 1. 题目描述

leetcode链接：154. 寻找旋转排序数组中的最小值 II

2. 思路分析

这道题与153. 寻找旋转排序数组中的最小值不一样的地方就是 nums 可能包含重复元素。所以需要判断nums[mid] == nums[right]，此时应该将 right 减 1 防止重复数字是最小元素。

3. 参考代码

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {  // 重复元素是最小元素
                right--;
            }
        }
        return nums[left];
    }
}

33. 搜索旋转排序数组 1. 题目描述

leetcode链接：33. 搜索旋转排序数组

2. 思路分析 3. 参考代码 81. 搜索旋转排序数组 II 1. 题目描述

leetcode链接：81. 搜索旋转排序数组 II

2. 思路分析 3. 参考代码 1760. 袋子里最少数目的球 1. 题目描述

leetcode链接：1760. 袋子里最少数目的球

2. 思路分析 3. 参考代码 1011. 在 D 天内送达包裹的能力 1. 题目描述

leetcode链接：1011. 在 D 天内送达包裹的能力

2. 思路分析 3. 参考代码 1482. 制作 m 束花所需的最少天数 1. 题目描述

leetcode链接：1482. 制作 m 束花所需的最少天数

2. 思路分析 3. 参考代码 4. 寻找两个正序数组的中位数 1. 题目描述

leetcode链接：4. 寻找两个正序数组的中位数

2. 思路分析 3. 参考代码

参考：

• 【LeetCode】﹝二分法ி﹞旋转排序数组的最小值、给定值查询
• 二分查找：为什么左右不对称？只比较mid与right的原因