当前位置：首页 > news >正文

【数据结构与算法】之二分查找

news 2024/10/22 11:39:09

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它通过比较数组中间元素与目标值来工作，从而将搜索范围缩小到一半，也称折半查找，是一种非常高效的工作于有序数组的查找算法。本文主要介绍二分查找及其几个变种，包括基础版、改变版、平衡版和Java版，以及Leftmost与Rightmost的概念。这些变种可能涉及对基本二分查找算法的优化或特定应用场景的调整。均采用Java语言实现。

一、基本原理

a 初始化：设置两个指针，一个指向数组的开始（i），另一个指向数组的结束（j）。
b 循环：当 i 小于或等于 j 时，执行以下操作：
- b1 计算中间位置 m：m = i + (j - i) / 2（建议采用 m = (i + j) >>> 1）。
- b2 比较中间元素 array[m] 与目标值：
  - 如果 array[m] 等于目标值，则查找成功，返回m。
  - 如果 array[m] 小于目标值，则将 i 更新为 m + 1，继续在数组的右半部分查找。
  - 如果 array[m] 大于目标值，则将 j 更新为 m - 1，继续在数组的左半部分查找。
c 结束：如果循环结束时没有找到目标值，则返回一个表示失败的标志（通常是-1）。

二分查找的时间复杂度为O(log n)，其中n是数组中的元素数量。这使得它在处理大数据集时非常高效。然而，二分查找要求数组必须是有序的，否则无法正确工作。

小细节：

在Java中，使用 >>> 无符号右移操作符来计算两个整数的平均值而不使用 “( j + i ) / 2” ，主要是出于以下几个原因：

避免溢出：当处理较大整数时，直接相加可能导致整数溢出。使用无符号右移可以避免这个问题，因为它不会进行实际的加法运算，而是通过位移来实现除以2的效果。
效率：位操作通常比算术操作更快。在性能敏感的应用中，使用位操作可以提高代码的执行效率。
整数除法：在Java中，整数除法会向下取整，这意味着如果两个数的和是奇数，直接除以2会得到一个较小的整数。使用无符号右移可以确保结果是一个整数，并且是两个数的中间值。
保持二进制位的对齐：在二分查找算法中，通常需要计算数组的中间索引。使用无符号右移可以确保计算出的中间索引是数组索引的有效值，避免了可能的负索引或越界问题。

示例代码

在二分查找中，我们通常需要计算数组的中间索引，如下所示：

int low = 0;
int high = array.length - 1; 
while (low <= high) { 
int mid = (low + high) >>> 1; // 进行比较和搜索操作 
}

在这个例子中，low 和 high 分别是搜索范围的起始和结束索引。使用 >>> 确保了即使 low 和 high 的和是一个奇数，计算出的 mid 也是一个有效的整数索引。（Java会自动将结果向下取整）

注意事项

负数处理：如果 low 或 high 是负数，使用无符号右移可能会导致不正确的结果，因为无符号右移会忽略符号位。在二分查找中，通常 low 和 high 都是非负数，所以这个问题不常见。
数据类型：确保使用的数据类型可以容纳计算结果。在Java中，整数溢出会导致意想不到的行为，尽管使用无符号右移可以减少溢出的风险。

总的来说，使用 >>> 无符号右移在Java中计算两个整数的平均值，是一种高效且安全的方法，特别是在需要处理大量数据或性能敏感的场合。

二、二分查找的各种形式

1) 基础版

在有序数组 A 内，查找值 target

如果找到返回索引
如果找不到返回 -1

public static int binarySearch(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;
}

i,j 对应着搜索区间 [0,a.length-1]（注意是闭合的区间），i<=j 意味着搜索区间内还有未比较的元素，i,j 指向的元素也可能是比较的目标
- 思考：如果不加 i==j 行不行？
- 回答：不行，因为这意味着 i,j 指向的元素会漏过比较
m 对应着中间位置，中间位置左边和右边的元素可能不相等（差一个），不会影响结果
如果某次未找到，那么缩小后的区间内不包含 m

2) 改变版

另一种写法

在有序数组 A 内，查找值 target

如果找到返回索引
如果找不到返回 -1

public static int binarySearch(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 (a[m] < target) {     // 在右边i = m + 1;} else {return m;}}return -1;
}

i,j 对应着搜索区间 [0,a.length)（注意是左闭右开的区间），i<j 意味着搜索区间内还有未比较的元素，j 指向的一定不是查找目标
- 思考：为什么这次不加 i==j 的条件了？
- 回答：这回 j 指向的不是查找目标，如果还加 i==j 条件，就意味着 j 指向的还会再次比较，找不到时，会死循环
如果某次要缩小右边界，那么 j=m，因为此时的 m 已经不是查找目标了

3) 平衡版

在有序数组 A 内，查找值 target

如果找到返回索引
如果找不到返回 -1

public static int binarySearchBalance(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;}}return (a[i] == target) ? i : -1;
}

思想：

左闭右开的区间，i 指向的可能是目标，而 j 指向的不是目标
不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 i）
- j - i > 1 的含义是，在范围内待比较的元素个数 > 1
改变 i 边界时，它指向的可能是目标，因此不能 m+1
循环内的平均比较次数减少了
时间复杂度 log(n)

4) Java 版

以下是Java内部的二分查找算法

private static int binarySearch0(long[] a, int fromIndex, int toIndex,long key) {int low = fromIndex;int high = toIndex - 1;
while (low <= high) {int mid = (low + high) >>> 1;long midVal = a[mid];
if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found.
}

例如 [1,3,5,6] 要插入 2 那么就是找到一个位置，这个位置左侧元素都比它小
- 等循环结束，若没找到，low 左侧元素肯定都比 target 小，因此 low 即插入点
插入点取负是为了与找到情况区分
-1 是为了把索引 0 位置的插入点与找到的情况进行区分

5) Leftmost 与 Rightmost (最左和最右)

有时我们希望返回的是最左侧的重复元素，如果用基础二分查找

对于数组 [1, 2, 3, 4, 4, 5, 6, 7]，查找元素4，结果是索引3
对于数组 [1, 2, 4, 4, 4, 5, 6, 7]，查找元素4，结果也是索引3，并不是最左侧的元素

以下是返回最左侧元素索引：

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;
}

以下是返回最右侧元素索引：

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;
}

6) Leftmost 与 Rightmost 的改动版

对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值，小于 traget的元素个数

Leftmost 改为

public static int binarySearchLeftmost(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; 
}

小于等于中间值，都要向左找

Rightmost 改为

public static int binarySearchRightmost(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;
}