wordpress 网站换域名,贵阳广告公司排名,电商平台规则,洛阳做网站哪家便宜二分查找#xff08;Binary Search#xff09;是一种在有序数组中查找特定元素的搜索算法。它通过比较数组中间元素与目标值来工作#xff0c;从而将搜索范围缩小到一半#xff0c;也称折半查找#xff0c;是一种非常高效的工作于有序数组的查找算法。本文主要介绍二分查找…二分查找Binary Search是一种在有序数组中查找特定元素的搜索算法。它通过比较数组中间元素与目标值来工作从而将搜索范围缩小到一半也称折半查找是一种非常高效的工作于有序数组的查找算法。本文主要介绍二分查找及其几个变种包括基础版、改变版、平衡版和Java版以及Leftmost与Rightmost的概念。这些变种可能涉及对基本二分查找算法的优化或特定应用场景的调整。均采用Java语言实现。
一、基本原理 a 初始化设置两个指针一个指向数组的开始i另一个指向数组的结束j。 b 循环当 i 小于或等于 j 时执行以下操作 b1 计算中间位置 mm 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]注意是闭合的区间ij 意味着搜索区间内还有未比较的元素i,j 指向的元素也可能是比较的目标 思考如果不加 ij 行不行 回答不行因为这意味着 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)注意是左闭右开的区间ij 意味着搜索区间内还有未比较的元素j 指向的一定不是查找目标 思考为什么这次不加 ij 的条件了 回答这回 j 指向的不是查找目标如果还加 ij 条件就意味着 j 指向的还会再次比较找不到时会死循环 如果某次要缩小右边界那么 jm因为此时的 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 边界时它指向的可能是目标因此不能 m1 循环内的平均比较次数减少了 时间复杂度 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;
} 大于等于中间值都要向右找
以上就是关于二分查找算法的各个版本感谢各位看官的观看下期见谢谢~
