7-2 二分查找

### 二分查找算法的实现与解析 #### 基本概念 二分查找是一种高效的查找算法，适用于已排序的数据结构。其核心思想是通过不断缩小搜索范围来快速定位目标值的位置[^2]。 #### 时间复杂度 相比于线性查找的时间复杂度 \(O(n)\)，二分查找的时间复杂度为 \(O(\log n)\)[^1]，这使得它成为处理大规模数据的理想选择。 #### 核心逻辑 在每次迭代过程中，计算中间索引 `mid` 并将其对应的值与目标值进行比较： - 如果目标值等于当前中间值，则找到目标； - 若目标值小于中间值，则继续在左半部分查找； - 否则，在右半部分查找[^3]。 以下是几种常见的应用场景及其具体实现： --- ### 寻找一个数 当只需要判断某个特定数值是否存在时，可采用如下方法： ```python def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 找到目标值返回索引 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # 未找到目标值 ``` 此版本仅用于确认目标值的存在与否并返回第一个匹配项的索引。 --- ### 寻找左侧边界 为了获取目标值首次出现的位置（即左边界），需调整条件以确保即使遇到相等的情况仍向左侧移动指针： ```python def find_left_bound(nums, target): left, right = 0, len(nums) - 1 res = -1 while left <= right: mid = (left + right) // 2 if nums[mid] >= target: # 当前值大于等于target时尝试更新res并向左逼近 if nums[mid] == target: res = mid right = mid - 1 else: left = mid + 1 return res ``` 上述代码实现了精确求解首个满足条件的元素位置的功能[^4]。 --- ### 寻找右侧边界 同理，若想得到最后一次出现的目标值所在处所对应的最大下标，则应修改终止规则以便于朝右边推进直至无法再进一步为止： ```python def find_right_bound(nums, target): left, right = 0, len(nums) - 1 res = -1 while left <= right: mid = (left + right) // 2 if nums[mid] <= target: # 只有当当前值不大于target才考虑记录结果并向右扩展区间 if nums[mid] == target: res = mid left = mid + 1 else: right = mid - 1 return res ``` 这种方法能够有效捕获最后符合条件的那个实例所在的坐标点位信息。 --- ### 综合应用案例 针对力扣第34题《在排序数组中查找元素的第一个和最后一个位置》，可以结合以上两种变体完成解答： ```python class Solution: def searchRange(self, nums, target): def findLeftBound(): l, r = 0, len(nums)-1 idx = -1 while l<=r: m=(l+r)//2 if nums[m]==target: idx=m r=m-1 elif nums[m]<target: l=m+1 else: r=m-1 return idx def findRightBound(): l,r=0,len(nums)-1 idx=-1 while l<=r: m=(l+r)//2 if nums[m]==target: idx=m l=m+1 elif nums[m]>target: r=m-1 else: l=m+1 return idx first_pos=findLeftBound() last_pos=findRightBound() return [first_pos,last_pos] if first_pos!=-1 and last_pos !=-1 else [-1,-1] ``` 该解决方案分别调用了两个辅助函数分别负责探测左右两端极限情形下的确切地址编号，并最终依据实际情况决定输出何种形式的结果集列表。 ---