知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 二分查找模板 ## 什么是二分查找 二分查找 = 每次砍掉一半,在**有序数组**中快速定位目标值。 ``` 暴力:从头到尾一个个找 → O(n) 二分:每次对半砍 → O(log n) n = 100万: 暴力:最多 100万 次 二分:最多 20 次(2^20 ≈ 100万) ``` ## 大白话理解 比如你在翻一本英语词典找单词 "middle": ``` 翻开词典中间 → 看到 "knowledge" "middle" 在 "knowledge" 前面 → 丢掉后半本 再翻前半本中间 → 看到 "apple" "middle" 在 "apple" 后面 → 丢掉前四分之一 再翻中间 → ...重复直到找到 ``` 这就是二分查找:每次排除一半,快速缩小范围。 ## 核心模板:闭区间 [l, r] 这是最常用、最不容易出错的模板。 ```java /** * 标准二分查找:在有序数组 nums 中查找 target * @return target 的下标,找不到返回 -1 */ public int binarySearch(int[] nums, int target) { int l = 0, r = nums.length - 1; // 闭区间 [l, r] while (l <= r) { // l > r 时退出,此时区间为空 int mid = l + (r - l) / 2; // 防止溢出,等价于 (l+r)/2 if (nums[mid] == target) { return mid; // 命中,直接返回 } else if (nums[mid] < target) { l = mid + 1; // target 在右半区,丢掉左边 } else { r = mid - 1; // target 在左半区,丢掉右边 } } return -1; // 没找到 } ``` ### 关键细节 ``` 1. while(l <= r):等号不能省 ┌───┬───┬───┐ │ 1 │ 3 │ 5 │ l=0, r=2, mid=1 → nums[1]=3 └───┴───┴───┘ target=5: l=mid+1=2, 此时 l=r=2, 还需要再判断一次 如果写成 while(l < r),会漏掉最后一个元素 2. mid = l + (r - l) / 2:防止溢出 l + r 可能超过 int 最大值(约 21 亿) l + (r - l) / 2 永远不会溢出 3. l = mid + 1, r = mid - 1:mid 已经判断过了,跳过它 如果不跳过 → 可能会死循环 ``` ## 半开区间模板 [l, r) 另一种写法,了解即可: ```java public int binarySearch(int[] nums, int target) { int l = 0, r = nums.length; // 半开区间 [l, r),r 不可达 while (l < r) { // 注意:没有等号 int mid = l + (r - l) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { l = mid + 1; } else { r = mid; // 注意:不 -1,因为 r 不可达 } } return -1; } ``` ``` 对比: 闭区间 [l,r] 半开区间 [l,r) 初始 l=0, r=n-1 l=0, r=n 循环条件 while(l <= r) while(l < r) 右缩 r = mid - 1 r = mid 左扩 l = mid + 1 l = mid + 1 终止 l > r(空区间) l == r(区间只剩一个元素) 推荐闭区间,不易出错。 ``` ## 三大标准变形 ### 1. 查找精确值 ```java // 上面已说完,直接套模板即可 ``` ### 2. 查找第一个 ≥ target 的位置(lowerBound / 下界) ```java /** * 在有序数组 nums 中,找第一个 >= target 的位置 * 如果 target > 所有元素,返回 nums.length */ public int lowerBound(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] >= target) { r = mid - 1; // 找到了一个候选,但可能是更后面的 → 继续往左找 } else { l = mid + 1; // 太小,去右边 } } // 退出时 l 指向第一个满足 >= target 的位置 return l; // l 在 [0, n] 范围内 } ``` ``` 为什么 l 是答案? nums = [1, 3, 5, 5, 7, 9], target = 5 初始: l=0, r=5 mid=2, nums[2]=5 >= 5 → r=1 mid=0, nums[0]=1 < 5 → l=1 mid=1, nums[1]=3 < 5 → l=2 l=2, r=1 → 退出 l=2 正是第一个 5 的位置 ✓ ``` ### 3. 查找第一个 > target 的位置(upperBound / 上界) ```java /** * 在有序数组 nums 中,找第一个 > target 的位置 * 如果 target >= 所有元素,返回 nums.length */ public int upperBound(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] > target) { r = mid - 1; // 找到了一个候选,继续往左找 } else { l = mid + 1; // 包括等于 target 的情况,都去右边 } } return l; } ``` ``` nums = [1, 3, 5, 5, 7, 9], target = 5 初始: l=0, r=5 mid=2, nums[2]=5 > 5? No → l=3 mid=4, nums[4]=7 > 5? Yes → r=3 mid=3, nums[3]=5 > 5? No → l=4 l=4, r=3 → 退出 l=4 是第一个 > 5 的位置(nums[4]=7)✓ ``` ## 过程模拟 ### 场景1:搜索 target = 5(存在) ``` nums = [1, 3, 5, 7, 9], target = 5 第1轮: l=0, r=4, mid=2 → nums[2]=5 == 5 → 返回 2 ✓ ``` ### 场景2:搜索 target = 6(不存在) ``` nums = [1, 3, 5, 7, 9], target = 6 第1轮: l=0, r=4, mid=2 → nums[2]=5 < 6 → l=3 ┌───┬───┬───┬───┬───┐ │ 1 │ 3 │ 5 │ │ │ ← 丢掉左边 └───┴───┴───┘───┴───┘ 第2轮: l=3, r=4, mid=3 → nums[3]=7 > 6 → r=2 ┌───┬───┬───┐ │ │ │ │ 7 │ 9 │ ← 丢掉右边 └───┴───┴───┘───┴───┘ 第3轮: l=3, r=2 → l > r,退出,返回 -1 ✓ ``` ### 场景3:搜索 target = 1(第一个元素) ``` nums = [1, 3, 5, 7, 9], target = 1 第1轮: l=0, r=4, mid=2 → nums[2]=5 > 1 → r=1 第2轮: l=0, r=1, mid=0 → nums[0]=1 == 1 → 返回 0 ✓ ``` ### 场景4:搜索 target = 9(最后一个元素) ``` nums = [1, 3, 5, 7, 9], target = 9 第1轮: l=0, r=4, mid=2 → nums[2]=5 < 9 → l=3 第2轮: l=3, r=4, mid=3 → nums[3]=7 < 9 → l=4 第3轮: l=4, r=4, mid=4 → nums[4]=9 == 9 → 返回 4 ✓ ``` ## 为什么 while(l <= r) 而不是 while(l < r)? ``` 考虑 target 是数组最后一个元素 [1,3,5,7,9] target=9: 若 while(l < r): l=0, r=4, mid=2 → 5<9 → l=3 l=3, r=4, mid=3 → 7<9 → l=4 l=4, r=4 → l < r 不成立,退出! 此时还没判断 nums[4] 是否等于 9,直接错过 若 while(l <= r): l=4, r=4 → 还会进入循环,mid=4 → nums[4]==9 → 返回 4 ✓ ``` ## 复杂度 - 时间:O(log n),每次循环区间减半 - 空间:O(1),只用了几个指针变量 ## 一句话总结 二分查找 = 在有序区间里每次对半砍。关键点:`while(l <= r)`、`mid = l + (r-l)/2` 防溢出、`l = mid+1` 和 `r = mid-1` 防死循环。 --- 下一篇:[02 - 搜索旋转排序数组](./02-search-rotated.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入