二分查找的三种形式&两道力扣

前言

过年前刷Leetcode的时候遇到这样一道题目：
354. 俄罗斯套娃信封问题 - 力扣（Leetcode）
其中使用patience sorting这个算法的做法中，因为牌堆顶是有序数组，所以可以使用二分查找把时间复杂度降到对数级别，但是这个并不是需要查找某个数字所出现的位置，而是需要查找当前数字需要插入到何处，思考了大佬的代码后恍然大悟，AC后想系统性整理一下二分查找的基本用法和拓展，于是有了此文。

二分查找基本用法（寻找某数位置）

//用kotlin是为了练一下语法……几乎和java是一样的，应该没有阅读压力
class Solution {  
    fun binarySearch(nums: IntArray, target: Int): Int {  
        var left: Int = 0  
        //right可以是nums.size-1，也可以是nums.size，具体情况写到下文  
        var right: Int = nums.size - 1  
        //while中的条件是一个关键点，什么时候取等什么时候不取等  
        while (left <= right) {  
            //经典操作，以防直接相加导致的越界  
            val mid = left + (right - left) / 2  
            //每次调整搜索范围时，什么时候加1什么时候不加1也是一个关键  
            if (nums[mid] < target) left = mid + 1  
            else if (nums[mid] > target) right = mid - 1  
            else if (nums[mid] == target) return mid  
        }  
        return -1  
    }  
}

在阅读labuladong大佬的文章前，对二分查找也存在很多疑问点，也就是我在代码注释中写出来的部分。因为本身也不经常刷算法，而接触二分查找又是大一入学阶段，所以导致当时的疑问就这么堆着，如果现在的话，最好的做法就是带着疑问，用多组testcase进行debug，一步步分析代码。

1.while中何时取等何时不取等

这个问题的关键在于right变量的初始化

right变量初始化为nums.size-1时，就可以取等，反之则不能
如果我们当前查找的区间形式是左闭右开，那么就可以取nums.size，反之则不能（很好想）。例如上述代码中查找区间形式为左闭右闭，while的终止条件为left>right（其实是right+1），这时闭区间内绝对不会存在数字，是一个非法区间，也就代表可以终止了，而终止的结果正是没有找到。
如果我们使用左闭右开区间，while的终止条件就是left>=right（其实就是right），这时假如区间左右端点相等，那么区间内还存在一个数字，但while循环却终止了，明显是错误的。可以如下改正

//改成right也可以，因为此时left和right相同了
return nums[left] == target ? left : -1;

2.left和right什么时候+1 or -1，什么时候不需要

这个问题的关键就承接第一个问题。当我们取的是闭区间的时候，每次搜索，mid这个索引下的数字都是被搜索了的，所以下一次我们理所应当应该取mid的左或右，而当我们取开区间时，mid这个索引下的数字存在未被搜索的情况，对应其未被搜索时，就需要从mid这个索引开始下一次搜索

寻找左侧边界的二分查找

fun binarySearchForLeftBound(nums: IntArray, target: Int): Int {  
    var left = 0  
    var right = nums.size - 1  
    while (left <= right) {  
        val mid = left + (right - left) / 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.size) return -1  
    return if (nums[left] == target) left  
    else -1  
}

1.while中何时取等

这个问题的解答和上面那个是相同的，不再赘述了

2.为什么上述代码可以搜索到左侧边界

因为每当nums[mid]==target时，我们都不直接返回当前下标，而是将右边界缩小，相当于不断向左进行收缩，进而寻找左侧边界

寻找右侧边界的二分查找

fun binarySearchForRightBound(nums: IntArray, target: Int): Int {  
    var left = 0  
    var right = nums.size - 1  
    while (left <= right) {  
        val mid = left + (right - left) / 2  
        if (nums[mid] > target) right = mid - 1  
        else if (nums[mid] < target) left = mid + 1  
        else if (nums[mid] == target) left = mid + 1  
    }  
    if (right < 0) return -1  
    return if (nums[right] == target) nums[right]  
    else -1  
}

其实上述代码中最后nums[right]==target部分中有些人习惯将right写为left-1，当while循环结束后，left=right+1，所以二者可以替换。但是这里为什么不去判断left而是判断left-1，就是一个疑惑点，这是因为每次我们都需要将mid这个下标排除出搜索区间，当循环结束时，左侧边界不断靠右且每次移动都有mid=left-1这个关系，最后left下标处一定不是target，反而是left-1处可能是target。

Leetcode 34

class Solution {

    fun searchRange(nums: IntArray, target: Int): IntArray {

        return if (nums.isEmpty()) intArrayOf(-1, -1)

        else intArrayOf(searchLeftBound(nums, target), searchRightBound(nums, target))

    }

  

    private fun searchLeftBound(nums: IntArray, target: Int): Int {

        var left = 0

        var right = nums.size - 1

        while (left <= right) {

            val mid = left + (right - left) / 2

            if (nums[mid] < target) left = mid + 1

            else if (nums[mid] > target) right = mid - 1

            else if (nums[mid] == target) right = mid - 1

        }

        if (left == nums.size) return -1

        return if (nums[left] == target) left

        else -1

    }

  

    private fun searchRightBound(nums: IntArray, target: Int): Int {

        var left = 0

        var right = nums.size - 1

        while (left <= right) {

            val mid = left + (right - left) / 2

            if (nums[mid] < target) left = mid + 1

            else if (nums[mid] > target) right = mid - 1

            else if (nums[mid] == target) left = mid + 1

        }

        if (left - 1 < 0) return -1

        return if (nums[left - 1] == target) left - 1

        else -1

    }

}

Leetcode 354

import java.util.Arrays;

  

/**

 * @author Zzh

 * @date 2023/1/7

 * @time 16:03

 */

class Solution {

    public int maxEnvelopes(int[][] envelopes) {

        Arrays.sort(envelopes, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);

        int[] height = new int[envelopes.length];

        for (int i = 0; i < envelopes.length; i++) {

            height[i] = envelopes[i][1];

        }

        return lengthOfLIS(height);

    }

  

    private int lengthOfLIS(int[] nums) {

        if (nums.length == 0) return 0;

        int[] top = new int[nums.length];

        int piles = 0;

        for (int poker :

                nums) {

            int left = 0;

            int right = piles - 1;

            while (left <= right) {

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

                if (top[mid] < poker) left = mid + 1;

                else if (top[mid] > poker) right = mid - 1;

                else if (top[mid] == poker) right = mid - 1;

            }

            if (left == piles) piles++;

            top[left] = poker;

        }

        return piles;

    }

}