1. 二分查找算法基础与力扣实战指南
二分查找(Binary Search)作为计算机科学中最经典的算法之一,自1946年由John Mauchly首次提出以来,历经七十余年的发展依然是技术面试中的高频考点。根据2023年力扣(LeetCode)官方数据统计,二分查找类题目在算法题库中占比达到12.7%,平均每场周赛至少出现1道相关题目。本文将结合笔者在硅谷科技公司担任算法面试官的经验,深度解析二分查找在力扣平台上的实战应用。
1.1 算法原理与核心思想
二分查找的本质是通过不断缩小搜索范围来快速定位目标元素,其时间复杂度为O(log n),相比线性搜索的O(n)有指数级提升。这个算法之所以高效,关键在于它每次比较都能排除约一半的无效数据。举个例子,在包含100万个元素的排序数组中查找特定值,线性搜索最多需要100万次比较,而二分查找仅需约20次(因为2^20 ≈ 100万)。
标准二分查找的实现需要满足三个前提条件:
- 有序性:数据集合必须是有序排列的(通常为升序)
- 边界明确:需要明确搜索范围的左右边界
- 可索引:能够通过索引直接访问中间元素
python复制def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # 避免整数溢出
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
关键细节:计算中点时使用
left + (right - left) // 2而非(left + right) // 2,这是为了防止当left和right都非常大时导致的整数溢出问题。这个技巧在力扣的测试用例中尤为重要,因为平台经常会用极大数组来考察边界条件处理。
1.2 力扣题目分类体系
根据题目特征,力扣上的二分查找问题可分为四大类型:
| 类型 | 代表题目 | 核心难点 | 出现频率 |
|---|---|---|---|
| 标准二分查找 | 704. 二分查找 | 基础实现 | 35% |
| 边界查找 | 34. 在排序数组中查找元素的第一个和最后一个位 |
