算法范式系列--二分算法
2023-07-15 17:48:48 #LeetCode #算法 #二分

算法范式系列–二分算法

  • 算法是Coder用来高效解决各种问题的屠龙刀，算法范式系列旨在武装自己的算法库。
  • 这次来强化二分算法技能，二分算法可是个好东西，高效，好用，真香！！！
  • 整理一些关于二分算法的想法以及刷题总结

一、关于二分算法

  • 可以使用二分算法的条件

    • 有序数列，（链表以及无序数组不行）

  • 复杂度

    • 时间复杂度：O(logN)
    • 空间复杂度：迭代实现O(1)，递归实现O(logN)

  • 二分算法的思想

    • 减治思想：不断缩小问题的规模
    • 排除法：排除掉不满足的区间

  • 什么时候该想到二分算法

    • 在一个有序数组中进行查找
      • 查找一个值，或者一个边界
      • 半有序也可以，比如旋转、山脉数组
    • 答案是二分的，即可以用排除法作为判断条件
    • 查找一个有范围的整数
    • 算法复杂度要求O(logN)

  • 二分查找循环体规定

    • [left, right], 双闭区间
    • 这个原则基本不变，之后的各种处理就比较统一了

二、二分算法解题思路

1. 能否用二分查找

  • 是否有序or半有序
  • 是否是查找一个有范围的整数
  • 二分判断条件是什么，排除条件是什么

2. 选择二分范式

范式一：在区间中查找特定的值

  • 区间分为左，中，右，三个部分
  • 比较简单的二分查找

范式二：查找一个整数区间中的一个值或者边界情况

  • 区间分为，已排除和未排除两个部分
  • 适用于处理分界以及复杂问题

3. 使用范式编写代码

范式一

  1. 编写三个区间的判断，并对区间进行进一步缩小
  2. 终止条件， left > right

范式二

  1. 编写排除条件
    • 根据题意排除区间，mid不包括在新区间中
  2. 编写待排除区间
    • 不用多虑，直接是上一个区间的反区间
  3. 检查mid的取值，向上取整还是向下
    • 左区间为满足条件时，要向上取整
      • 标志：else部分 left = middle
    • 右区间为满足条件时，要向下取整
      • 标志：else部分 right = middle
    • 取整错误，区间缩小为2的时候，无法继续缩小下去了
  4. 检查查找结束后的left是否覆盖题意的范围
    • 默认返回范围在，[left, right]中
    • 有时候查找结果可能超出这个区间，比如right位置的下一个
    • 两种解决
      1. 特别判断
      2. 在设置初始循环体时，将边界条件囊括其中。（推荐）
        • 比如，right一般取len-1，但有时候，结果范围包括len时，right取len

三、二分查找的两个编程范式

  • 二分可以通过迭代以及递归实现，推荐使用迭代实现。
  • 这里仅提供迭代实现的两个范式，递归的能不用就不用。
  • 避免mid溢出：int mid = left + ( right - left) /2;

二分范式一

  • 擅长查找特定的值，查找到了则直接返回结果。
  • 其将区间分为 left，mid，right三个区间，分别对这三个区间进行判断。
  • 终止条件：left > right, 即while(left <= right)
    • 终止后，left和right的取值情况不好确定
    • 所以只擅长精准查找并返回，不擅长查找结束后的处理
    • 如果需要查找边界等情况，推荐使用范式二
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int binarySearchFor(int[] nums, int target) {
        int result = -1;
        int left = 0, right = nums.length - 1; // 闭区间
        while (left <= right) { // left > right 终止
            int mid = left +（ right - left) / 2; // 避免mid溢出
            if (nums[mid] == target) {  // 三段条件判断
                result = mid;
                break;
            } else if (nums[mid] < target) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        return result;
    }

二分范式二

  • 擅长处理各种边界查找问题
  • 原理思想：通过不断将不满足区间条件一边排除，不断缩小范围，最终left便为查找结果。
    • 如果mid不在满足条件的区间，则将该区间包括mid，排除掉
    • 如果mid在满足条件的区间，则再缩小区间时候，保留mid
  • 需要抽取出区间选择条件，即大于等于，小于等于之类的
  • 终止条件：left == right, 即 while(left < right)
    • 查找终止后，left的位置是比较明确的，就是查找元素的边界位置
    • 至于是之后取上边界还是下边界，再进一步判断
  • mid 取整：
    • 主要是第二个条件分支中的left=mid和right=mid语句造成的
      • 目的是，当区间长度为2时，能进一步缩小区间。
      • 当为left=mid，区间长度为2时，如果向下取整，则区间永远为2，死循环。
      • 同理right=mid, 区间长度为2时，如果向上取整，则区间永远为2，死循环。
    • 如果排除的是左区间，则向下取整
      • int mid = left + (right - left) / 2;
    • 如果排除的是右区间，则向上取整
      • int mid = left + (right - left + 1) / 2;
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    // 排除左区间
    int binarySearchFor(int[] nums, int target) {
        int left = 0, right = nums.length-1; // right也可能取nums.length，看查找结果的范围
        while (left < right) { // 注意，不是 <=
            int mid = left + (right - left) / 2;
            if ( mid 不满足区间条件 ) { 
                // 将左区间完全排除
                left = mid + 1
            } else {
                // mid满足区间，所以包含mid
                right = mid
            }
        }
    }
    // 排除右区间
    int binarySearchFor(int[] nums, int target) {
        int left = 0, right = nums.length-1; // right也可能取nums.length，看查找结果的范围
        while (left < right) { // 注意，不是 <=
            int mid = left + (right - left + 1) / 2;
            if ( mid 不满足所在区间 ) { 
                // 将右区间完全排除
                right = mid - 1
            } else {
                // mid满足区间，所以包含mid
                left = mid
            }
        }
    }

四、一些LeetCode典型题目

1. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
LeetCode地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {

        // 查找第一个大于等于target的位置

        int left = 0, right = nums.length;

        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}

2. x 的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int mySqrt(int x) {

        if(x == 0) return 0;
        if(x==1) return 1;
        int left = 0; 
        int right = x/2;

        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if( mid > x / mid ){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return left;
    }
}

3. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int minEatingSpeed(int[] piles, int H) {

        int maxK = 0;
        for(int i =0; i< piles.length; i++){
            maxK = Math.max(maxK,piles[i]);
        }
        int left = 1, right = maxK;
        while(left < right){
            int mid = left + (right - left ) /2;
            if(!canEatOut(piles,H,mid)){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    private boolean canEatOut(int [] piles, int H,int k){
        int count = 0;
        for(int i = 0; i < piles.length; i++){
            int total = piles[i];
            count += total / k;
            if(total % k != 0) count++;
        }
        return count <= H;
    }
}

4. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 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]
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1,-1};
        return new int []{findLowBound(nums,target),findUpBound(nums,target)};
    }

    // 找第一个大于等于
    private int findLowBound(int[] nums, int target){
        int left = 0, right = nums.length-1;
        while (left<right){
            int mid = left + (right-left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return nums[left] != target? -1:left;
    }
    // 第一个小于等于
    private int findUpBound(int [] nums,int target){
        int left = 0, right = nums.length-1;
        while (left<right){
            int mid = left + (right-left+1) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        return nums[left] != target? -1:left;
    }
}

5. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right-left )/2;
            if(nums[mid] == target){ 
                return mid;
            }else if(nums[mid] < target){
                if(nums[mid] < nums[left] && nums[right] < target){
                    right = mid -1;
                }else{
                    left = mid+1;
                }
            }else{
                if(nums[mid] >= nums[left] && nums[left] > target){
                    left = mid+1;
                }else{
                    right = mid -1;
                }
            }
        }
        return -1;
    }
}

6. 搜索旋转排序数组 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length == 1) return nums[0] == target;
        int left = 0, right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left )/2;
            if(nums[mid] == target) return true;
            // 解决重复问题：移动一格
            if(nums[mid] == nums[right]) {
                right--;
                continue;
            }
            if(nums[mid] < target){
                // 最小值出现在左区间，且最小值不能到头
                if(nums[mid] < nums[right] && nums[right] < target){
                    right = mid -1;
                }else{ // 正常向右
                    left = mid + 1;
                }
            }else{
                // 最小值出现在右区间，且targe必然不在左
                if(nums[mid] > nums[right] && nums[left] > target){
                    left = mid + 1;
                }else{ // 正常向左
                    right = mid -1;
                }
            }
        }
        return false;
    }
}

7.寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMin(int[] nums) {
        if(nums[0] <= nums[nums.length-1]) return nums[0];
        int left =0, right = nums.length-1;
        while( left < right){
            int mid = left + (right - left ) / 2;
            // 排除法，正常情况下，最小应该直接选左边区间，但排除一下这种情况
            if(nums[mid] > nums[right] ){
                // 左边单调增，且旋转分界点在右边区间
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
}

8. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int lengthOfLIS(int[] nums) {
        int [] tails = new int[nums.length];
        int index = 0;
        for(int i = 0; i < nums.length; i++){
            int pos = findFirstLarge(tails, index, nums[i]);
            tails[pos] = nums[i];
            if(pos == index) index++;
        }
        return index;
    }
    // 查找第一个大于自己的位置
    private int findFirstLarge(int [] tails,int size, int target){
        int left = 0, right = size;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(tails[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}

9.寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length -1;
        while( left < right ){
            int mid = left + (right - left) / 2;
            int count = 0; // 统计nums中小于等于mid的个数
            for(int i = 0; i< nums.length; i++){
                if(nums[i] <= mid) count++;
            }
            // 鸽巢原理
            if(count > mid){
                // count个数，这些数位于1-mid，count比mid大，则这些数中必有重复的
                right = mid;
            }else{
                left = mid +1; // 上边区间的相反
            }
        }
        return left;
    }
}

10.猜数字大小

猜数字游戏的规则如下：
每轮游戏，系统都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，系统会告诉你这个数字比系统选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1 : 系统选出的数字比你猜测的数字小
1 : 系统选出的数字比你猜测的数字大
0 : 恭喜！你猜对了！
示例 :
输入: n = 10, pick = 6
输出: 6
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while(left < right){
            int mid = left + (right - left + 1) /2;
            if(guess((int)mid) < 0){
                // mid 大了
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return (int)left;
    }
}

11.寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       if(nums1.length > nums2.length){
            int [] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int left = 0, right = nums1.length-1;
        int len = nums1.length + nums2.length;
        while (left < right) {
            int i = (left + right+1) / 2; // 向上取整
            int j = len/2 - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i-1;
            } else {
                left = i;
            }
        }
        int i = left;
        int j = len/2 - i;
        int maxLeftNums1 = i == 0? Integer.MIN_VALUE:nums1[i-1];
        int minRightNums1 = i== nums1.length? Integer.MAX_VALUE:nums1[i];
        int maxLeftNums2 = j == 0? Integer.MIN_VALUE:nums2[j-1];
        int minRightNums2 = j==nums2.length? Integer.MAX_VALUE:nums2[j];
        if(( len & 1) == 1){
            return (double) Math.min(minRightNums1,minRightNums2);
        }else{
            return (double) (Math.min(minRightNums1,minRightNums2) + Math.max(maxLeftNums1,maxLeftNums2)) / 2.0;
        }
    }
}

12. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。 
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 0, right = n;
        while(left < right){
            int mid = left + (right-left) / 2;
            if(!isBadVersion(mid)){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

13. 找到 K 个最接近的元素

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。
示例 1:
输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]
示例 2:
输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]
题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {

        int left = 0, right = arr.length;
        LinkedList<Integer> result = new LinkedList();

        while(left < right){
            int mid = left + (right - left) /2;

            if(arr[mid] < x){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        // left 为第一个 大于等于 x的
        int front = left -1, back = left;
        while(result.size() < k){
            if(front < 0 
            || back < arr.length && Math.abs(arr[front]-x) > Math.abs(arr[back]-x)){
                result.addLast(arr[back]);
                back++;
            }else{
                result.addFirst(arr[front]);
                front--;
            }
        }
        return result;
    }
}
Prev
2023-07-15 17:48:48 #LeetCode #算法 #二分
Next