1. 二分查找算法基础解析
二分查找(Binary Search)作为计算机科学中最经典的算法之一,其核心思想就像我们查字典时的翻页策略。想象一下,当你查找以字母"M"开头的单词时,绝不会从字典第一页开始逐页翻阅,而是直接翻到中间位置,根据当前页字母决定向前或向后查找——这正是二分查找的精髓。
在力扣(LeetCode)题库中,二分查找类题目通常具有以下特征:
- 输入数据已排序(或经过预处理后可排序)
- 要求时间复杂度优于O(n)
- 需要寻找特定元素或确定边界位置
算法的时间复杂度为O(log n),这意味着对于包含10亿个元素的数组,最多只需30次比较就能找到目标(因为2^30≈10亿)。这种指数级的效率提升,使其成为处理大规模数据时的首选方案。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 力扣典型二分查找题型分类
2.1 基础查找型
代表题目:704. 二分查找
python复制def 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
关键点:
- 循环条件
left <= right确保区间有效性 - 中间位置计算防止整数溢出应写作
mid = left + (right - left) // 2 - 每次迭代至少排除一半数据
2.2 边界查找型
代表题目:34. 在排序数组中查找元素的第一个和最后一个位置
python复制def searchRange(nums, target):
def find_left():
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + righ
