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

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

🎬个人简介：努力学习ing
📋本专栏：python刷题专栏
📋其他专栏：C语言入门基础以及python入门基础
🎀CSDN主页 愚润求学

一，视频题目

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

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

class Solution:# 因为只考虑数对之和是否满足条件，所以排序不影响结果def less_equal(self, nums: List[int], target: int, start: int, end: int) -> int:left, right = start, endwhile left <= right:mid = (left + right) // 2if nums[mid] < target:left = mid + 1else:right = mid - 1return leftdef countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:ans = 0n = 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) - 1ans += end - start + 1return 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) // 2if citations[-mid] >= mid:left = mid + 1 # [mid + 1, right]内再判断是否有更大的helse:right = mid - 1return 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 = 1while left <= right:mid = (left + right) // 2if sum((p - 1) // mid + 1 for p in piles) <= h:right = mid - 1 # 满足条件向左收缩找更小的,[left, mid-1] # 即循环不变量right + 1 始终为trueelse:left = mid + 1return 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) // 2if sum(mid // t for t in time) >= totalTrips:right = mid - 1else:left = mid + 1return 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 = 0mx = min(stock) + budgetdef check(num:int, comp :List[int]) -> bool:money = 0for s, base, c in zip(stock, comp, cost):if s < base * num:money += (base * num - s) * cif money > budget:return Falsereturn Truefor comp in composition:left, right = ans + 1, mx # ans+1: 1，寻找更大数；2，防止当没有更小数的时候，ans返回left-1while left <= right:mid = (left + right) // 2if check(mid, comp):left = mid + 1else:right = mid - 1ans = left - 1return ans

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

bisect_left函数：

class Solution:def minimizeArrayValue(self, nums: List[int]) -> int:def check(limit: int) -> bool:extra = 0for i in range(len(nums) - 1, 0, -1):extra = max(nums[i] + extra - limit, 0)return nums[0] + extra <= limitreturn 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-1price.sort()def f(d:int) -> int:cnt = 1pre = price[0] # 最大值for p in price:if p - pre >= d:  cnt += 1pre = p # 更新最大值，如果与最大值之差都小于甜蜜值，则代表之前的小值也满足要求return cntleft, right = 0, price[-1] - price[0]while left <= right:mid = (left + right) // 2if f(mid) >= k:left = mid + 1else:right = mid - 1return left - 1

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

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！