《算法通关之路》-chapter5二分法网站首页 学无止境

《算法通关之路》-chapter5二分法

Jiawen9 2024-06-17 10:29:44

简介《算法通关之路》-chapter5二分法

《算法通关之路》学习笔记，记录一下自己的刷题过程，详细的内容请大家购买作者的书籍查阅。

二分查找

力扣第704题
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

'''
方法一：递归
时间复杂度：O（logn）
空间复杂度：O（logn）
'''
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        def binary_search(left: int, right: int, target: int) -> int:
            if left > right:
                return -1
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                return binary_search(left, mid - 1, target)
            else:
                return binary_search(mid + 1, right, target)
        
        return binary_search(left, right, target)

nums, target = [-1,0,3,5,9,12], 9
solu = Solution()
solu.search(nums, target)

'''
方法一：迭代
时间复杂度：O（logn）
空间复杂度：O（1）
'''
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right :
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

nums, target = [-1,0,3,5,9,12], 9
solu = Solution()
solu.search(nums, target)

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

力扣第153题
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

'''
方法一：二分法
时间复杂度：O（logn）
空间复杂度：O（1）
'''
class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if left == right:
                return nums[mid]
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
        return -1

nums = [3,4,5,1,2]
solu = Solution()
solu.findMin(nums)

爱吃香蕉的珂珂

力扣第875题
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

'''
方法一：二分法
时间复杂度：O（mlogn）
空间复杂度：O（1）
'''
import math
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:

        def eat(k, h):
            need_h = 0
            for pile in piles:
                need_h += math.ceil(pile / k)
            return need_h <= h

        res = -1
        left, right = 1, max(piles)
        while left <= right:
            mid = left + (right - left) // 2
            if eat(mid, h):
                res = mid
                right = mid - 1
            else:
                left = mid + 1
        return res

piles, h = [3,6,7,11], 8
solu = Solution()
solu.minEatingSpeed(piles, h)

二分查找的变种（防止死循环）

# 1. 在排序数组中找到第一个大于或等于x的元素，该元素必定存在
def bs(nums, x):
    l, h = 0, len(nums) - 1
    while l <= h:
        mid = l + (h - l) // 2
        if l == h:
            break
        elif nums[mid] >= x:
            h = mid
        else:
            l = mid + 1

# 2. 在排序数组里找到最后一个小于或等于x的元素，该元素必定存在
def bs(nums, x):
    l, h = 0, len(nums) - 1
    while l <= h:
        mid = l + (h - l) // 2
        if l == h or l + 1 == h:
            break
        elif nums[mid] <= x:
            l = mid
        else:
            h = mid - 1
    return nums[h] if nums[h] <= x else nums[l]

x 的平方根

力扣第69题
给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

'''
方法一：二分法
时间复杂度：O（logn）
空间复杂度：O（1）
'''
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

x = 8
solu = Solution()
solu.mySqrt(x)

寻找峰值

力扣第162题
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

'''
方法一：二分法
时间复杂度：O（logn）
空间复杂度：O（1）
'''
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if mid + 1 < len(nums) and nums[mid] < nums[mid + 1]:
                left = mid + 1
            elif mid > 0 and nums[mid] < nums[mid - 1]:
                right = mid - 1
            else:
                return mid
        return -1

nums = [1,2,3,1]
solu = Solution()
solu.findPeakElement(nums)

分割数组的最大值

力扣第410题
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。

'''
方法一：二分+贪心
时间复杂度：O（nlogm）
空间复杂度：O（1）
'''
class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        left, right = max(nums), sum(nums)
        
        def helper(ans: int) -> bool:
            cnt, cur = 1, 0
            for num in nums:
                if cur + num > ans:
                    cur = num
                    cnt += 1
                else:
                    cur += num
            return cnt <= k

        while left <= right:
            mid = left + (right - left) // 2
            if left == right:
                return left
            elif helper(mid):
                right = mid
            else:
                left = mid + 1
        return -1
    
nums, m = [7,2,5,10,8], 2
solu = Solution()
solu.splitArray(nums, m)

逆向思维二分法求解模板

def helper(x):
    # 判断是否可行的函数

# 搜索区间
l, h = max(nums), sum(nums)

# 根据实际情况调整二分逻辑
# 这里情况可以是找任意满足条件的值、最左满足条件的值，最右满足条件的值等
while l <= h:
    mid = l + (h - l) // 2
    if l == h:
        return l
    elif helper(mid):
        h = mid
    else:
        l = mid + 1
return -1