🍋引言
二分查找是一种高效的搜索算法，特别适用于有序数组。它通过将待查找区间逐渐缩小一半的方式，快速定位目标元素。在本文中，我们将深入探讨二分查找算法的原理、应用场景以及实现方式。
🍋基本原理
二分查找的基本原理是不断缩小待查找区间，通过比较中间元素与目标值的大小来确定下一步搜索的方向。这种分而治之的思想使得算法的时间复杂度保持在 O(log n) 的水平，是一种非常高效的搜索算法。
🍋算法步骤
初始化左右边界：设定初始的搜索区间，通常为整个数组。 计算中间索引：通过计算左右边界的中点来确定中间索引。 比较中间元素：将中间索引对应的元素与目标值进行比较。 调整搜索范围：根据比较结果，调整左右边界，缩小搜索范围。 重复执行：重复以上步骤，直到找到目标元素或搜索范围为空。
🍋应用场景
有序数组搜索： 二分查找最常见的应用场景是在有序数组中查找元素。 搜索区间问题： 可以用于解决搜索区间的问题，如在旋转有序数组中查找最小值。 近似查找： 用于查找最接近目标值的元素。
🍋例题
有的题并没有使用二分查找
🍋1608. 特殊数组的特征值
给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
class Solution(object): def specialArray(self, nums): """ :type nums: List[int] :rtype: int """ if all(element == 0 for element in nums) == True: return -1 count1 = 0 for i in range(1, len(nums) + 1): # 1,2 for j in range(len(nums)): if nums[j] >= i: count1 += 1 if count1 != i: count1 = 0 continue else: return i return -1
🍋2389. 和有限的最长子序列
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
from itertools import accumulate from bisect import bisect_left, bisect_right class Solution: def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]: nums.sort() s = list(accumulate(nums)) return [bisect_right(s, q) for q in queries] # def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]: # nums.sort() # m = len(queries) # ans = [0] * m # idx = sorted(range(m), key=lambda i: queries[i]) # s = j = 0 # for i in idx: # while j < len(nums) and s + nums[j] <= queries[i]: # s += nums[j] # j += 1 # ans[i] = j # return ans
🍋744. 寻找比目标字母大的最小字母
给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。
返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。
from bisect import bisect_right class Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: position_right = bisect_right(letters, target) if position_right == len(letters): return letters[0] return letters[position_right]
🍋704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution: def search(self, nums: List[int], target: int) -> int: low = 0 high = len(nums)-1 while low<=high: mid = low + (high-low)//2 if nums[mid] == target: return mid elif nums[mid]>target: high = mid - 1 else: low = mid + 1 return -1
🍋888. 公平的糖果交换
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。
两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。
返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。
class Solution: def swap(self,a, b): return b, a # def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]: # 超时 # result1 = 0 # result2 = 0 # l_ = [] # for i in range(len(aliceSizes)): # for j in range(len(bobSizes)): # aliceSizes[i],bobSizes[j] = self.swap(aliceSizes[i],bobSizes[j]) # if sum(bobSizes) == sum(aliceSizes): # l_.append(bobSizes[j]) # l_.append(aliceSizes[i]) # return l_ # aliceSizes[i], bobSizes[j] = self.swap(aliceSizes[i], bobSizes[j]) def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]: # sum(aliceSizes)-A+B=sum(bobSizes)-B+A # A-B=tmp=(sum(aliceSizes)-sum(bobSizes))//2 tmp = (sum(aliceSizes) - sum(bobSizes)) >> 1 for a in aliceSizes: if a - tmp in bobSizes: return [a, a - tmp]
🍋268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
class Solution: def missingNumber(self, nums: List[int]) -> int: # for i in range(len(nums)+1): # if i not in nums: # return i # 过了，但是太慢 nums.sort() for i, num in enumerate(nums): if num != i: return i return len(nums)
🍋278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
# The isBadVersion API is already defined for you. # def isBadVersion(version: int) -> bool: class Solution: def firstBadVersion(self, n: int) -> int: low = 0 high = n-1 while low<=high: mid = low + (high-low)//2 if isBadVersion(mid)==True : high = mid - 1 else: low = mid + 1 return low
挑战与创造都是很痛苦的，但是很充实。
