Leetcode 二分法问题总结(超详细!!!)
in 算法 with 0 comment

Leetcode 二分法问题总结(超详细!!!)

in 算法 with 0 comment

0x00 循环不变式

初始化:它在循环的第一轮迭代开始之前,应该是正确的。

保持:如果在某一次循环迭代开始之前是正确的,那么在下一次迭代开始之前,它也应该保持正确(假设当循环变量等于k时符合,再看执行一遍循环体后是否还符合循环不变式)。

终止:循环能够终止,并且可以得到期望的结果。(这一步是和数学归纳法不同的一点,用循环不变式则更进一步,数学归纳法到这里就得出了一个关系式就结束,而用循环不变式,不但要先确保一个正确的关系式,还要看最后循环结束时,循环变量最后等于多少,根据循环不变式推导是否符合自己的要求。)。

只要保障上述三者成立,那么这个循环就是正确的。下列问题全部是在输入数组是升序的情况下讨论。

0x01 准确查找问题

区间为[a, b)类型。

初始化:我们假设都给定了正确类型的numstarget

保持:当nums[mid] == target的时候,显然我们找到了target,我们直接返回mid即可。当target > nums[mid]的时候,此时[l, mid]中的元素全部小于target,此时target只会存在于[mid+1, r)这个区间中。当target < nums[mid]的时候,此时[mid, r)这个区间内的元素全部大于target,此时target只会存在于[l, mid-1]区间内,此时为了保障区间类型的统一,我们将[l, mid-1]变成[l, mid)

终止:当l==r,此时区间[l, r)中没有元素了,那么target就不在nums中。

class Solution:
    def find(self, nums, target):
        """
        :type nums: List[int]
        :type target: int 
        :rtype: int
        """
        l, r = 0, len(nums)
        while l < r:
            mid = (l + r)//2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                l = mid + 1
            else:
                r = mid
        return -1

区间为[a, b]类型

初始化:我们假设都给定了正确类型的numstarget

保持:当nums[mid] == target的时候,显然我们找到了target,我们直接返回mid即可。当target > nums[mid]的时候,此时[l, mid]中的元素全部小于target,此时target只会存在于[mid+1, r]这个区间中。当target < nums[mid]的时候,此时[mid, r]这个区间内的元素全部大于target,此时target只会存在于[l, mid-1]区间内。

终止:当l > r,此时区间[l, r]中没有元素了,那么target就不在nums中。

class Solution:
    def find(self, nums, target):
        """
        :type nums: List[int]
        :type target: int 
        :rtype: int
        """
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r)//2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                l = mid + 1
            else:
                r = mid - 1
        return -1

对于后面的问题,我们都按照[a, b]这种区间类型分析。

0x02 lower_bound & upper_bound问题

lower_bound回答的问题:在一个有序数组arr中, 寻找大于等于target的元素的第一个索引,如果存在, 则返回相应的索引index,否则, 返回arr的元素个数 n

保持:当nums[mid] == target的时候,显然我们找到了target,但是我们需要找的是第一个大于等于target的元素,所以我们需要在[l, mid-1]中继续寻找。当target > nums[mid]的时候,此时[l, mid]中的元素全部小于target,此时大于等于target的元素只会存在于[mid+1, r]这个区间中。当target < nums[mid]的时候,此时[mid, r]这个区间内的元素一定大于target,此时target只会存在于[l, mid-1]这个区间内。

终止:当l>r,此时区间[l, r]中没有元素了,而l是大于等于target的第一个位置(很容易分析,假设l==r的时候target == nums[mid],此时r=mid-1l=mid)。

相关问题:

Leetcode 35:搜索插入位置(最详细的解法!!!)

class Solution:
    def lower_bound(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l + r)//2
            if target <= nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        return l

upper_bound回答的问题:在一个有序数组arr中, 寻找大于target的元素的第一个索引,如果存在, 则返回相应的索引index,否则, 返回arr的元素个数 n

初始化:我们假设都给定了正确类型的numstarget

保持:当nums[mid] == target的时候,显然我们找到了target,但是我们需要找的是第一个大于target的元素,所以我们需要在[mid+1, r]中继续寻找。当target > nums[mid]的时候,此时[l, mid]中的元素全部小于target,此时大于等于target的元素只会存在于[mid+1, r]这个区间中。当target < nums[mid]的时候,此时[mid, r]这个区间内的元素一定大于target,此时target只会存在于[l, mid]这个区间内。

终止:当l>r,此时区间[l, r]中没有元素了,而l是大于target的第一个位置(分析同上)。

class Solution:
    def upper_bound(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l + r)//2
            if target >= nums[mid]:
                l = mid + 1
            else:
                r = mid - 1
        return l

0x03 floor & ceil 问题

floor回答的问题:如果找到target,返回第一个target相应的索引index;如果没有找到target, 返回比target小的最大值相应的索引, 如果这个最大值有多个, 返回最大索引;如果这个target比整个数组的最小元素值还要小, 则不存在这个targetfloor值, 返回-1

其实这就是一个upper_bound问题,我们最后只要判断target==nums[l](需要保证l<len(nums)),如果成立返回l,否则返回l-1

相关问题:

Leetcode 34:在排序数组中查找元素的第一个位置和最后一个位置(最详细的解法!!!)

class Solution:
    def floor(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l + r)//2
            if target <= nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
                
        if l < len(nums) and nums[l] == target:
            return l
        
        return l-1

ceil回答的问题:如果找到target,返回最后一个target相应的索引index;如果没有找到target,返回比target大的最小值相应的索引,如果这个最小值有多个,返回最小的索引;如果这个target比整个数组的最大元素值还要大,则不存在这个targetceil值, 返回整个数组元素个数n

其实这就是一个upper_bound问题,我们最后只要判断target==nums[l-1],如果成立返回l-1,否则返回l(需要保证l<len(nums))。

相关问题:

Leetcode 34:在排序数组中查找元素的第一个位置和最后一个位置(最详细的解法!!!)

class Solution:
    def ceil(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l + r)//2
            if target >= nums[mid]:
                l = mid + 1
            else:
                r = mid - 1
                
        if nums[l-1] == target:
            return l-1
        if l < len(nums):
            return l
        return -1

其实很多变种问题都是通过lower_boundupper_bound变化而来,所以一定要先理解基础问题。

0x04 python 中的库

import bisect
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

0x05 cpp中的库

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
auto lower = std::lower_bound(data.begin(), data.end(), 4);
auto upper = std::upper_bound(data.begin(), data.end(), 4);

0x06 终极方法

看了上面这么多问题和概念,相信你可能已经有点迷糊了。我们不妨回去问题的最初,二分法问题更本质的到底是什么?其实二分解决的问题本质问题就是,当我们对一个问题分开考虑的时候,其中一半肯定可以去除。那么问题的核心就是左半边保留还是右半边保留?所以对于区间[l, r],有如下两种方案

第一种,左半边[l, mid]保留

while l < r:
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid + 1
return l

第一种,右半边[mid, r]保留

while l < r:
    mid = (l + r + 1) // 2
    if check(mid):
        l = mid
    else:
        r = mid - 1
return l

所以问题的关键就是这个check函数,判断我们最后要找的值是在左,还是在右。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

reference:

http://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html

https://github.com/liuyubobobo/Play-with-Algorithms

https://blog.csdn.net/mountzf/article/details/51866342

https://segmentfault.com/a/1190000016825704

https://docs.python.org/3/library/bisect.html

https://zh.cppreference.com/w/cpp/algorithm/lower_bound

https://zh.cppreference.com/w/cpp/algorithm/upper_bound

https://www.acwing.com/blog/content/31/

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses