本文介绍 Java 中二分查找的基础实现、边界处理及溢出优化，对比线性查找的时间复杂度。详细分析了大 O 表示法下的渐进上界、下界及紧界，涵盖空间复杂度计算。此外，还探讨了平衡版、插入点及重复元素场景下的二分查找变体，并结合 LeetCode 经典题目进行代码实操演示。
需求：在有序数组 A 内，查找 target
如果找到返回索引；如果找不到返回 -1
/*二分查找基础版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回索引 找不到返回 -1 */
public static int binarySearchBasic {
, j = a.length - ;
(i <= j) {
(i + j) >>> ;
(target < a[m]) {
j = m - ;
} (a[m] < target) {
i = m + ;
} {
m;
}
}
-;
}
为什么 while 循环条件是 i<=j，不是 i<j？
i=j 指向的共同元素被省略。
(i+j)/2 有无问题呢？
假设这是一个极大的数组 i=0,j=Integer.MAX_VALUE-1
m=1073741823，此时 target>m，重新开始 i=m+1
此时 m=(i+j)/2=-536870913 超过了 Java 表示正整数范围
可以使用右移一位来运算
int m = ( i + j ) >>> 1
也可以试试
int m = i + ( j - i ) / 2
统一一下大于号，小于号方向，符合有序数组升序的美感，提高可读性
/*二分查找基础版 Plus Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回索引 找不到返回 -1 */
public static int binarySearchBasic(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
//目标在左边
if (target < a[m]) {
j = m - 1;
//目标在右边
} else if (a[m] < target) {
i = m + 1;
} else {
return m;
}
}
return -1;
}
/*二分查找改动版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回索引 找不到返回 -1 */
public static int binarySearchAlternative(int[] a, int target) {
int i = 0, j = a.length; //第一处
while (i < j) { //第二处
int m = (i + j) >>> 1;
//目标在左边
if (target < a[m]) {
j = m; //第三处
//目标在右边
} else if (target > a[m]) {
i = m + 1;
} else {
return m;
}
}
return -1;
}
第一处若不修改，当查找到元素数组中没有时就会陷入死循环 (i=j=m)
边界划分从左闭右闭变成左闭右开，j 是不可能取到的，只是右开的一个边界
/*线性查找 Params:a-待查找的升序数组 (可以是有序数组) target-待查找的目标值 Returns:找到返回索引 找不到返回 -1 */
public static int linearSearch(int[] a, int target) {
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
return i;
}
}
return -1;
}
这种就是我们最经常写的查找格式，但是效率比二分查找要低
依赖测试数据普遍有效，具有区别性，来有效体现不同算法的优劣
依赖硬件属性，算法的运行快也有可能是硬件配置好
前提：分析算法最差的执行情况，假设每行语句执行时间相同
最差情况：找不到
数组元素个数为 n
| 语句 | 执行次数 | 总和 |
|---|---|---|
| int i = 0 | 1 | 3*n+3 |
| i < a.length | n+1 | |
| i++ | n | |
| a[i] == target | n | |
| return -1 | 1 |
最差情况：找不到 (比数组最大的元素大)
{ 1 [2,3,4,5,6] 7 } 找不到 7 比找不到 1 要更慢 (原因，中间值向下取整)
数组元素个数为 n
while 循环次数 L=floor(log₂(n))+1
| 语句 | 执行次数 | 总和 |
|---|---|---|
| int i = 0,j = a.length - 1 | 2 | 5*L+4 |
| i <= j | L+1 | =( floor(log₂(n)) + 1 )*5+4 |
| int m = (i + j) >>> 1 | L | |
| target < a[m] | L | |
| a[m] < target | L | |
| i = m + 1 | L | |
| return -1 | 1 |
大 O 表示法
时间复杂度是用来衡量：一个算法的执行，随数据规模增大，而增长的时间成本。不依赖环境因素 (硬件，软件)
代表算法执行最差情况。
f(n)=3*n+3
g(n)=n
取 c=4，在 n0=3 之后，g(n) 可以作为 f(n) 的渐进上界，大 O 表示法写作 O(n)
f(n)=5*floor(log₂(n))+9
g(n)=log₂(n)
O(log₂(n))
| 时间复杂度从上到下是从低到高 | O(1) | 常量时间，意味着算法时间并不随数据规模而变化 |
|---|---|---|
| O(log(n)) | 对数时间 | |
| O(n) | 线性时间，算法时间与数据规模成正比 | |
| O(n*log(n)) | 拟线性时间 | |
| O(n^2) | 平方时间，类似还有立方时间等等 | |
| O(2^n) | 指数时间 | |
| O(n!) | 阶乘 |
代表算法执行最佳情况
既能代表算法执行最差情况，也能代表算法执行最佳情况
与时间复杂度类似，一般也是使用 O 表示法来衡量：一个算法执行随数据规模增大，而增长的额外空间成本
二分查找的空间复杂度：需要常数个指针 i，j，m，3*4=12
因此额外占用的空间是 O(1)
在二分查找基础版中，假设 while 循环体循环了 L 次
当目标元素出现在有序数组的最左边 比较语句 L 次
当目标元素出现在有序数组的最右边 比较语句 2*L 次
平衡问题解决方案
/*二分查找平衡版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回索引 找不到返回 -1 */
public static int binarySearch(int[] a, int target) {
int i = 0, j = a.length;
while (1 < j - i) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m;
} else {
i = m;
}
}
if (target == a[i]) {
return i;
} else {
return -1;
}
}
不在循环内找出，等范围内只剩 i 时，退出循环，在循环外比较 a[i] 与 target
平均比较次数变小。但是改动之前如果 target 在数组的中间，执行最佳情况，时间复杂度 O(1)；修改过后时间复杂度没有最好和最优情况了，时间复杂度 Θ(log(n))
/*二分查找基础插入点版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回索引 找不到返回 -1 */
public static int binarySearchBasicInsertionPoint(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
//目标在左边
if (target < a[m]) {
j = m - 1;
//目标在右边
} else if (a[m] < target) {
i = m + 1;
} else {
return m;
}
}
return -(i + 1);
}
i 就是我未在该数组中发现目标元素，但是如果要插入数组，它所对应的索引
/*二分查找 Leftmost1 版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回最左侧重复元素索引 找不到返回 -1 */
public static int binarySearchLeftmost1(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m;
j = m - 1;
}
}
return candidate;
}
/*二分查找 Rightmost1 版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:找到返回最右侧重复元素索引 找不到返回 -1 */
public static int binarySearchRightmost1(int[] a, int target) {
int i = 0, j = a.length - 1;
int candidate = -1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else if (a[m] < target) {
i = m + 1;
} else {
candidate = m;
i = m + 1;
}
}
return candidate;
}
不论是重复元素最左侧索引，还是重复元素最右侧索引，大部分代码与基础版没有差别，关键就是在最后 a[m]==target 的情况下，做了保留索引并更新。
但是最后的返回值都是 -1，具体实际意义并不明显
/*二分查找 Leftmost2 版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:返回>=target 的最靠左的索引 */
public static int binarySearchLeftmost2(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target <= a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
/*二分查找 Rightmost2 版 Params:a-待查找的升序数组 target-待查找的目标值 Returns:返回<=target 的最靠右的索引 */
public static int binarySearchRightmost2(int[] a, int target) {
int i = 0, j = a.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < a[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i - 1;
}
在实际应用中，对于一个已知升序数组
求排名 Leftmost(target) + 1(数组索引从 0 开始，排名从 1 开始，所以加 1)
求前任 Leftmost(target) - 1
求后任 Rightmost(target) + 1
小于目标索引 0 ~ Leftmost(target) - 1
小于等于目标索引 0 ~ Rightmost(target)
大于目标索引 Rightmost(target) + 1 ~ 数组长度 - 1
大于等于目标索引 Leftmost(target) ~ 数组长度 - 1
最基本，基础版，平衡板均可，较为简单，不做讲解
public class P704 {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (target < nums[mid]) {
right = mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
插入点版本，较为简单，不做讲解
public class P35_1 {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (target < nums[mid]) {
right = mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
}
还可以使用二分查找 Leftmost 版 (忽略有序数组是否有重复元素，虽然题目明确说了没有重复元素)
public class P35_2 {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
使用 Leftmost(target) 和 Right(target)
public class P34_1 {
public int[] searchRange(int[] nums, int target) {
return new int[]{left(nums, target), right(nums, target)};
}
public int left(int[] a, int target) {
int left = 0, right = a.length - 1;
int candidate = -1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (target < a[mid]) {
right = mid - 1;
} else if (a[mid] < target) {
left = mid + 1;
} else {
candidate = mid;
right = mid - 1;
}
}
return candidate;
}
public int right(int[] a, int target) {
int left = 0, right = a.length - 1;
int candidate = -1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (target < a[mid]) {
right = mid - 1;
} else if (a[mid] < target) {
left = mid + 1;
} else {
candidate = mid;
left = mid + 1;
}
}
return candidate;
}
}
可以将两个方法结合
public class P34_2 {
public int[] searchRange(int[] nums, int target) {
int leftBound = binarySearch(nums, target, true);
int rightBound = binarySearch(nums, target, false);
return new int[]{leftBound, rightBound};
}
public int binarySearch(int[] a, int target, boolean isLeft) {
int left = 0, right = a.length - 1;
int candidate = -1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (target < a[mid]) {
right = mid - 1;
} else if (a[mid] < target) {
left = mid + 1;
} else {
candidate = mid;
if (isLeft) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return candidate;
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online