我要评论一、核心概念 & 前提条件
1. 什么是二分查找
二分查找（折半查找）：在有序区间内，每次取中间元素对比，排除一半区间，逐步缩小范围，快速定位目标值。本质：分治思想，每次砍掉一半数据，查询效率远高于遍历。
2. 必备前提（必背，不满足不能用）
- 数组 / 集合必须有序（升序 / 降序）
- 支持随机访问（数组、
arraylist适合；linkedlist不适合，无下标随机访问）
3. 时间复杂度
- 最优：\(o(1)\)（一次命中）
- 最坏 / 平均：\(o(\log_2 n)\)对比：顺序遍历 \(o(n)\)，数据量越大，二分优势越明显。
二、基础实现（两种写法：循环版 + 递归版）
生产环境优先循环版；递归版仅用于理解思想，不推荐线上使用。
写法 1：循环实现（标准升序二分，最常用）
场景：有序数组，查找目标值 target，返回下标；不存在返回 -1
public class binarysearch {
// 标准二分查找（升序数组）
public static int binarysearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
// 循环条件：左指针 <= 右指针
while (left <= right) {
// 计算中间下标（防溢出写法）
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
// 找到目标，返回下标
return mid;
} else if (arr[mid] < target) {
// 目标在右区间，左指针右移
left = mid + 1;
} else {
// 目标在左区间，右指针左移
right = mid - 1;
}
}
// 遍历完未找到
return -1;
}
public static void main(string[] args) {
int[] nums = {1, 3, 5, 7, 9, 11, 13};
system.out.println(binarysearch(nums, 7)); // 3
system.out.println(binarysearch(nums, 4)); // -1
}
}
写法 2：递归实现（理解用，不推荐生产）
public static int binarysearchrecursive(int[] arr, int left, int right, int target) {
// 递归出口：区间不存在
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarysearchrecursive(arr, mid + 1, right, target);
} else {
return binarysearchrecursive(arr, left, mid - 1, target);
}
}
递归缺点：数据量大、查找深度深时，会触发 stackoverflowerror 栈溢出。
三、核心关键点（编码必记，面试必考）
1. 中间值 mid 两种写法 & 整数溢出问题
错误写法（经典坑）
int mid = (left + right) / 2;
问题：当 left 和 right 都是接近 integer.max_value 时，两数相加溢出，变成负数，数组下标越界。
正确写法（工程通用）
int mid = left + (right - left) / 2;
原理：先算差值再除 2，永远不会溢出。
2. 循环条件 left <= right 还是 left < right
left <= right（标准查找：精准找目标值）区间是 [left, right]，左右指针都有效，区间内元素全部判断。left < right（查找边界、左右区间、第一个 / 最后一个目标值）常用于：找左边界、右边界、大于 / 小于目标的第一个元素。
3. 指针移动规则（死循环重灾区）
以升序为例：
arr[mid] < target：目标在右侧 →left = mid + 1arr[mid] > target：目标在左侧 →right = mid - 1
❌ 禁止写 left = mid / right = mid（大概率死循环）。
4. 数组顺序区分
上面代码基于升序；如果是降序数组，大小判断逻辑反转即可。
四、进阶场景：二分查找边界（笔试 / 算法高频）
实际业务常遇到：数组存在重复元素，需要找：
- 目标值第一次出现的下标（左边界）
- 目标值最后一次出现的下标（右边界）
示例数组：[1,2,2,2,3,4]，找 target=2
1. 查找左边界（第一个 2）
// 返回第一个等于 target 的下标；无则返回-1
public static int findleftbound(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 最后校验是否等于目标
return arr[left] == target ? left : -1;
}
2. 查找右边界（最后一个 2）
public static int findrightbound(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
// 向上取整，避免死循环
int mid = left + (right - left + 1) / 2;
if (arr[mid] <= target) {
left = mid;
} else {
right = mid - 1;
}
}
return arr[left] == target ? left : -1;
}
关键点：找右边界时，
mid需要向上取整，否则死循环。
五、项目实战运用场景（工作中怎么用）
- 有序数据快速检索商品编号、用户 id、字典编码等有序数组 / 列表查询，替代全量遍历，提升性能。
- 查找边界值
- 分页区间定位
- 分数区间划分（评级、等级判定）
- 时间有序日志区间筛选
- 旋转有序数组查找（算法题）部分有序的特殊数组（如
[4,5,6,1,2,3]）二分变种。 - 平方根、开方计算用二分逼近法计算
√x，替代数学公式。 - 海量有序数据分片大数据分片、分桶，快速定位数据所在分片。
六、二分算法 经典坑点 + 原因 + 解决方案（重点背诵）
坑 1：未保证数组有序，直接使用二分
现象
结果随机错误、找不到存在的元素。
原因
二分核心依赖有序，无序数组逻辑完全失效。
解决
使用前先排序；业务保证数据本身有序。
坑 2：(left + right) / 2 整数溢出
现象
下标变成负数，抛出 arrayindexoutofboundsexception 数组越界。
原因
left 和 right 接近 integer.max_value，相加超出 int 范围。
解决
统一使用安全写法：int mid = left + (right - left) / 2。
坑 3：指针更新错误，导致死循环（最高发）
错误示例
// 错误：left = mid 会死循环
if (arr[mid] < target) {
left = mid;
}
原因
当 left 和 right 相邻时，mid 永远等于 left，区间不再收缩，循环永不退出。
解决
标准查找：left = mid + 1、right = mid - 1；边界场景严格对应指针规则。
坑 4：循环条件 left <= right 和 left < right 混用
现象
漏查元素、边界查找结果错误。
区分
- 精准查找单个元素 →
left <= right - 查找左右边界、区间划分 →
left < right
坑 5：重复元素场景，直接用基础二分
现象
只能查到重复元素中任意一个，无法拿到第一个 / 最后一个。
解决
改用边界二分（左边界 / 右边界专用代码）。
坑 6：递归版二分，大数据量栈溢出
现象
stackoverflowerror
解决
生产环境一律使用循环迭代版，递归仅用于学习演示。
坑 7：对 linkedlist 使用二分查找
现象
性能极差，退化为全量遍历。
原因
linkedlist 基于链表，不支持 o (1) 随机访问，获取 arr[mid] 需要遍历下标。
解决
二分只用于数组、arraylist 这种支持随机访问的结构。
坑 8：忽略数组为空 / 空指针
现象
nullpointerexception / 数组下标异常。
解决
方法开头做非空判断：
if (arr == null || arr.length == 0) {
return -1;
}
七、二分算法优化 & 拓展
- 插值查找二分是固定折半，插值根据目标值动态计算
mid，适合分布均匀的有序数组。 - 斐波那契查找利用斐波那契数列分割区间，适合有序 + 大多在左侧的数据。
- 二分 + 哈希有序数组二分定位下标，结合哈希表处理重复数据。
日常开发标准二分足够，插值 / 斐波那契仅算法面试了解即可。
八、面试高频简答题（直接背诵）
二分查找前提是什么？数据必须有序，且支持随机访问。
为什么
(left+right)/2会溢出？怎么解决？两数之和超出 int 最大值；改用left + (right - left) / 2。二分查找时间复杂度？\(o(\log n)\)，远优于顺序遍历。
二分查找死循环一般是什么原因？指针更新错误（
left=mid/right=mid）、循环条件使用不当。数组有重复元素，如何找到目标第一个 / 最后一个位置？使用左边界、右边界专用二分逻辑，调整指针和循环条件。
九、终极背诵口诀
二分查找先有序，随机访问是前提；mid 计算防溢出，左加差值除以二；精准查找小于等于，边界查找小于号；指针移动加减一，防止循环死到底；重复元素找边界，两套逻辑要分清；链表不用递归弃，空数组先判安全第一。
到此这篇关于java二分查找(二分算法)的文章就介绍到这了,更多相关java二分查找算法内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论