核心基础考点#

1. 二分查找的本质与前提：二分查找是基于分治思想的高效查找算法，核心前提是查找表为有序静态序列，时间复杂度为$O(\log n)$，是408查找章节的核心高频考点。
2. 基础实现细节
   • 迭代实现标准模板：初始化左边界left=0，右边界right=n-1，循环条件常用left <= right，每次计算中间下标mid = left + (right - left) / 2（避免left+right溢出），根据nums[mid]与目标值target的大小关系更新边界：若nums[mid] == target则返回mid；若nums[mid] < target则left = mid +1；反之right = mid -1。
   • 递归实现：通过递归调用缩小查找区间，空间复杂度为$O(\log n)$，工程中更推荐迭代版以避免栈溢出。
3. 常考变种题型
   • 查找第一个大于等于target的元素（下界查找）
   • 查找最后一个小于等于target的元素（上界查找）
   • 旋转有序数组的二分查找（无重复元素/有重复元素场景）
   • 寻找峰值元素、寻找旋转数组的最小值等拓展题型
4. 易错点梳理：边界条件混淆、mid计算溢出、未提前校验序列有序性直接使用二分查找，这些都是历年真题的常见失分点。