【2025-02-25】基础算法：二分查找（一）

用户11029137

发布于 2025-02-26 08:14:34

14500

代码可运行

运行总次数：0

代码可运行

📝前言说明： ●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频 ●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。 ●文章中的理解仅为个人理解。 ●文章中的截图来源于B站博主灵茶山，如有侵权请告知。

一，视频题目

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

题目：

二分查找简述（闭区间情况）：

循环不变量：每次迭代的前后始终为真的结论. 开区间：不含端点

闭区间的写法，L要更新为M+1，不能更新成M，因为M已经被访问过了。R更新成M-1 左闭右开区间：初始化时R应该指向下标n，更新时，R更新成M，L更新成M+1 开区间：L初始化成-1，R 初始化成n，更新时，L和R都更新成M（下界-1，上界+1）注意：不同写法的循环不变量不同，要自行判断

上面图解示例为>=，当遇到其他不等号时可以进行转换，把其他的用>=转换解释： 1，找>target 的位置：找>=target+1的位置 2，找<target 的位置：先找到>=target的位置，然后左移一个位置 3，找<=target的位置：先找到>=target+1的位置。然后左移一个位置题解：开始位置：>=的位置；结束位置：<=的位置

class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)   [start == len(nums) 的原因，这时候也代表target不存在]，即left所指向的一定是第一个>=target的数。如果target不存在，就会指向下标 n（注意这时候下标n是越界的）
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 闭区间 [left, right]
        while left <= right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right+1] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1  # 范围缩小到 [left, mid-1]
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right]
        # 循环结束后 left = right+1
        # 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]

二，课后作业

1，2529. 正整数和负整数的最大计数

题解：

class Solution:
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  
        while left <= right:  
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1 
            else:
                left = mid + 1 
        return left # left 始终指向第一个 >= target 的元素下标

    def maximumCount(self, nums: List[int]) -> int:
        neg, pos = 0,0
        neg = self.lower_bound(nums, 0)
        pos = len(nums) - self.lower_bound(nums, 1)
        return neg if neg > pos else pos

2，2300. 咒语和药水的成功对数

class Solution:
    def less_equal(self, nums:List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        # 1，先得到每个咒语的最小成功组合的药水强度min = (success // spells[i]) + 1
        # 2, 对于每个spells里面的元素，找到potions里面min的下标，然后求得可成功组合的数目存入pairs
        n, m = len(spells), len(potions)
        pairs = [0] * n
        potions.sort()
        for i in range(0, n):
            if success % spells[i] == 0:
                mi = success // spells[i]
            else:
                mi = success // spells[i] + 1
            start = self.less_equal(potions, mi)
            if start != m:
                pairs[i] = m - start
            else:
                pairs[i] = 0
        return pairs

3，2563. 统计公平数对的数目

class Solution:
    # 因为只考虑数对之和是否满足条件，所以排序不影响结果
    def less_equal(self, nums: List[int], target: int, start: int, end: int) -> int:
        left, right = start, end
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        ans = 0
        n = len(nums)
        nums.sort()
        for i in range(n):
            start = self.less_equal(nums, lower - nums[i], i + 1, n-1)
            end = self.less_equal(nums, upper - nums[i] + 1, i + 1, n - 1) - 1
            ans += end - start + 1
        return ans

4，275. H 指数 II

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 1, len(citations)
        # 注意：这里的查找区间是数字：[left, right]，即 h 指数[1,n]而数组citations只是用来决定收缩方向的
        while left <= right:
            mid = (left + right) // 2
            if citations[-mid] >= mid:
                left = mid + 1 # [mid + 1, right]内再判断是否有更大的h
            else:
                right = mid - 1
        return left - 1

5，875. 爱吃香蕉的珂珂

题目：

向上取整的技巧：

生成器表达式（写法和列表推导式类似，但是用()，更节省内存）：

# 生成器表达式
gen_expr = (i * 2 for i in range(5))
print(gen_expr)  # 输出: <generator object <genexpr> at 0x7f...>

题解：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 速度查找区间：[1, max(piles)]
        n = len(piles)
        right = max(piles)
        left = 1
        while left <= right:
            mid = (left + right) // 2
            if sum((p - 1) // mid + 1 for p in piles) <= h:
                right = mid - 1 # 满足条件向左收缩找更小的,[left, mid-1] # 即循环不变量right + 1 始终为true
            else:
                left = mid + 1
        return right + 1

6，2187. 完成旅途的最少时间

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        # 查找区间：[1，n * max(time)]
        n = len(time)
        left, right = 1, totalTrips * min(time)
        while left <= right:
            mid = (left + right) // 2
            if sum(mid // t for t in time) >= totalTrips:
                right = mid - 1
            else:
                left = mid + 1
        return right + 1

7，2861. 最大合金数

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        # 分别判断每个机器能制造出的最大合金数，二分查找可以制造的数量[1, min(stock)+budget]
        ans = 0
        mx = min(stock) + budget
        def check(num:int, comp :List[int]) -> bool:
            money = 0
            for s, base, c in zip(stock, comp, cost):
                if s < base * num:
                    money += (base * num - s) * c
                    if money > budget:
                        return False
            return True
        for comp in composition:
            left, right = ans + 1, mx # ans+1: 1，寻找更大数；2，防止当没有更小数的时候，ans返回left-1
            while left <= right:
                mid = (left + right) // 2
                if check(mid, comp):
                    left = mid + 1
                else:
                    right = mid - 1
            ans = left - 1
        return ans

8，2439. 最小化数组中的最大值

bisect_left函数：

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        def check(limit: int) -> bool:
            extra = 0
            for i in range(len(nums) - 1, 0, -1):
                extra = max(nums[i] + extra - limit, 0)
            return nums[0] + extra <= limit
        return bisect_left(range(max(nums)), True, lo=min(nums), key=check)

9，2517. 礼盒的最大甜蜜度

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        # 因为甜蜜度的最大值越大，则至多能选择的糖果数量越少
        # 二分查找甜蜜度的最大值
        # f(d): 当前甜蜜值至少为d时，则至多有f(d)数量的糖果
        # f(d) >= k，说明答案至少为d，f(d) < k，说明答案至多为d-1
        price.sort()
        def f(d:int) -> int:
            cnt = 1
            pre = price[0] # 最大值
            for p in price:
                if p - pre >= d:  
                    cnt += 1
                    pre = p # 更新最大值，如果与最大值之差都小于甜蜜值，则代表之前的小值也满足要求
            return cnt
        left, right = 0, price[-1] - price[0]
        while left <= right:
            mid = (left + right) // 2
            if f(mid) >= k:
                left = mid + 1
            else:
                right = mid - 1
        return left - 1

总结： 1，固定一种自己的写法（闭区间） 2，找准判断条件 3，找准搜索区间和收缩方向 4，找准答案的循环不变量

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-25，如有侵权请联系 cloudcommunity@tencent.com 删除

基础