1.二分查找算法初识
1.1 简介
二分查找算法，也称折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。
1.2 实现思路
- 初始状态下，将整个序列作为搜索区域；
- 找到搜索区域内的中间元素，和目标元素进行比对；
- 如果相等，则搜索成功；
- 如果中间元素大于目标元素，表明目标元素位于中间元素的左侧，将左侧区域作为新的搜素区域；
- 反之，若中间元素小于目标元素，表明目标元素位于中间元素的右侧，将右侧区域作为新的搜素区域；
- 重复执行第二步，直至找到目标元素。如果搜索区域无法再缩小，且区域内不包含任何元素，则表明整个序列中没有目标元素，查找失败。
2.二分查找基础版-查找范围左闭右闭
2.1 需求分析
需求：在有序数组A 内，查找值 targetValue
- 如果找到返回索引
- 如果找不到返回−1
2.2 算法描述
2.3 代码实现
/** * 二分查找基础版 * * @param array 待查找的升序数组 * @param targetValue 待查找的目标值 * @return 找到则返回目标值的索引，找不到返回-1 */ public static int binarySearchBasic(int[] array, int targetValue) { // 设置指针 left 指向数组的开始索引位置 int left = 0; // 设置指针 right 指向数组的最后索引位置 int right = array.length - 1; // 定一个 mid，表示 left 和 right 的中间索引位置 int mid; /* 对 [left,right] 范围内的元素进行查找，left <= right 成立说明在 [left,right] 范围内还有元素可以可以查找 while循环退出的两种方式： - 进入了 else，说明找到了，返回中间索引 - 不满足 left <= right，说明范围不断缩小后依旧没有找到，退出循环 */ while (left <= right) { // 查找中间索引，如果 (left+right)/2 为小数则会自动向下取整 mid = (left + right) / 2; if (targetValue < array[mid]) { // 如果 目标值 小于 中间索引值，说明 目标值索引 应该在 中间索引 的左边 // 我们可以通过调整 right 的值缩小查找范围 right = mid - 1; } else if (array[mid] < targetValue) { // 如果 目标值 大于 中间索引值，说明 目标值索引 应该在 中间索引 的右边 // 我们可以通过调整 left 的值缩小查找范围 left = mid + 1; } else { // 否则说明 目标值 等于 中间索引值，也就说明我们找到了 return mid; } } // 走到这里说明没有进入过上面 while 中的else，while循环退出时 left > right // 说明没有找到 return -1; }
3.基础版的几个问题
3.1 循环条件不加 left == right 行不行
不行，因为这意味着当 left 和 right 相等时，会漏掉 left 和 right 共同指向的元素会漏过与目标值的比较。
3.2 left + right 超过int最大值问题
我们先来举个模拟例子：
public static void main(String[] args) { // 模拟 二分查找中的 left int left = 100; // 模拟 二分查找中的 right int right = Integer.MAX_VALUE - 1; // 此时 left+right 的值超过了 int范围 的最大值，导致 left + right 的结果为负数 // 然后对负数进行除以2操作，结果依旧为负数 int mid = (left + right) / 2; // 输出结果为 -1073741775 System.out.println(mid); }
那如何解决这个问题呢？我们可以使用 位运算 来代替 /2 的操作。
- 算数右移
>>：低位溢出，符号位不变，并用符号位补溢出的高位。- 逻辑右击（无符号右移）
>>>：低位溢出，高位补0。由于最高位符号位为0表示该数为正数，因此相比于
>>做到了能将一个 负数 无符号右移后变成 正数。
/** * 二分查找增强版 * * @param array 待查找的升序数组 * @param targetValue 待查找的目标值 * @return 找到则返回目标值的索引，找不到返回-1 */ public static int binarySearchPlus(int[] array, int targetValue) { int left = 0; int right = array.length - 1; int mid; while (left <= right) { /* 考虑到 left+right 的值可能会超过 int可表示 的最大值，我们不再对他们的和直接除以2 我们知道 除以2 的操作可以用 位运算 >>1 来代替 但还不够，由于 (left+right) 值溢出表示负数，>>1 只是做 除以2 操作，最高位符号位不变，依旧为1表示负数，负数除以2依旧是负数 这时候我们可以修改为 无符号右移 >>>1 ，低位溢出，高位补0，那么最高位符号位为0就表示正数了 */ mid = (left + right) >>> 1; if (targetValue < array[mid]) { right = mid - 1; } else if (array[mid] < targetValue) { left = mid + 1; } else { return mid; } } return -1; }
4.二分查找改变版-查找范围左闭右开
right 只是作为一个边界，指向的一定不是查找目标。
/** * 二分查找改变版 * * @param array 待查找的升序数组 * @param targetValue 待查找的目标值 * @return 找到则返回目标值的索引，找不到返回-1 */ public static int binarySearchPlus(int[] array, int targetValue) { // 设置指针 left 指向数组的开始索引位置 int left = 0; // 设置指针 right 指向查找范围的后一个索引位置 // 在这里 right 只是作为一个边界，指向的一定不是查找目标。 int right = array.length; int mid; // 在 [left,right) 左闭右开的区间范围内进行目标值查找 // 因为 right 只是一个边界不作为查找索引，因此不能将 left <= right 作为条件 while (left < right) { mid = (left + right) >>> 1; if (targetValue < array[mid]) { // 目标值 小于 中间索引值，则应该将右范围缩小 // 需要将查找范围变为 [left,mid) right = mid; } else if (array[mid] < targetValue) { left = mid + 1; } else { return mid; } } return -1; }
5.衡量算法的好坏-时间复杂度
5.1 两种算法代码语句执行次数
🍀 二分查找
public static int binarySearchBasic(int[] a, int target) { // 设置指针和初值 int i = 0; int j = a.length - 1; // L 次 元素在最左边 L 次， 元素在最右边 2*L 次 while (i <= j) { // 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; } /* 1 [2,3,4,5] 5 右侧没找到更差 int i = 0, j = a.length - 1; 2 return -1; 1 元素个数 循环次数 4-7 3 floor(log_2(4)) = 2+1 8-15 4 floor(log_2(8)) = 3+1 16-31 5 floor(log_2(16)) = 4+1 32-63 6 floor(log_2(32)) = 5+1 ... ... 循环次数L = floor(log_2(n)) + 1 i <= j L+1 int m = (i + j) >>> 1; L target < a[m] L a[m] < target L i = m + 1; L 代码执行次数公式：(floor(log_2(n)) + 1) * 5 + 4 当n=4时，(3) * 5 + 4 = 19*t 当n=1024时，(10 + 1) * 5 + 4 = 59*t */
🍀 线性查找
/** * <h3>线性查找</h3> * * @param a 待查找的升序数组 (可以不是有序数组) * @param target 待查找的目标值 * @return <p>找到则返回索引</p> * <p>找不到返回 -1</p> */ public static int linearSearch(int[] a, int target) { for (int i = 0; i < a.length; i++) { if (a[i] == target) { return i; } } return -1; } // 1. 最差的执行情况 // 2. 假设每行语句执行时间一样 t /* 数据元素个数 n int i = 0; 1 i < a.length; n+1 i++ n a[i] == target n return -1; 1 算法运行语句总次数：3*n + 3 当n=4时，3*4 + 3 = 15*t 当n=1024时，3*1024 + 3 = 3075*t */
5.2 代码执行次数图形化比较
采用 Desmos | 图形计算器 工具对两种算法的代码执行次数进行比较。
- x 轴表示数组的数据量大小。
- y 轴表示代码语句执行次数。
二分查找算法执行次数公式：3⋅x+3
线性查找算法执行次数公式：
当数组数据量比较小，即 x 值比较小的时候，执行次数比较为：
当数组数据量比较大，即 x 值比较大的时候，执行次数比较为：
5.3 大O表示法图形化比较
二分查找算法：O(log(n))
线性查找算法：O(n)
6.二分查找性能
6.1 时间复杂度
- 最坏情况：O(log n)
- 最好情况：如果待查找元素恰好在数组中央，只需要循环一次 O(1)
6.2 空间复杂度
- 需要常数个指针 left，right， mid，因此额外占用的空间是O(1)
7.二分查找平衡版
/** * <h3>二分查找平衡版</h3> * * <ol> * <li>不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)</li> * <li>i 指针可能是查找目标</li> * <li>j 指针不可能是查找目标</li> * <li>因为 1. 2. 3. 当区域内还剩一个元素时, 表示为 j - i == 1</li> * <li>改变 i 边界时, m 可能就是目标, 同时因为 2. 所以有 i=m</li> * <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 3. 所以有 j=m</li> * <li>三分支改为二分支, 循环内比较次数减少</li> * </ol> * * @param a 待查找的升序数组 * @param target 待查找的目标值 * @return <p>找到则返回索引</p> * <p>找不到返回 -1</p> */ public static int binarySearchBalance(int[] a, int target) { int i = 0, j = a.length; while (1 < j - i) { // 范围内待查找的元素个数 > 1 时 int m = (i + j) >>> 1; if (target < a[m]) { // 目标在左边 j = m; } else { // 目标在 m 或右边 i = m; } } return (target == a[i]) ? i : -1; }
思想：
- 左闭右开的区间，i 向的可能是目标，而 j 指向的不是目标
- 不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 i）
- j − i > 1 的含义是，在范围内待比较的元素个数 > 1
- 改变 i 边界时，它指向的可能是目标，因此不能 m + 1
- 循环内的平均比较次数减少了
- 时间复杂度 Θ(log(n)) （最坏最好情况）
