本文解释基于线性结构的二分查找算法,并给出几种实现的代码示例。
需求场景
假设电商系统中,每天大量用户访问产品页面,用户可以设置低于一定价格的条件过滤产品,并从过滤结果中选择商品加入购物车。因每秒同时有大量用户通过设置价格上限过滤产品,结果展示需要非常块。
后端在产品列表采用线性搜索算法与用户输入价格进行比较,然后返回符合条件的产品。这样时间复杂度为O(n). 这意味着产品越多,效率越低。如果我们对产品按价格排序进行存储,然后使用二分查找,那么实现时间复杂度为O(log n). 使用二分搜索,搜索结果所花费的时间也会随着数据集的增长而增加,但不是成正比例增加。
实现二分算法
二分算法简言之,与数组中间元素比较key值,如果不相等,则其中一半不在考虑,然后继续搜索剩下的一半,直至找到对应值。当然关键是数组已排序,如果搜索已结束仍未发现则表明结果不在数组中。
迭代实现
public int runBinarySearchIteratively(int[] sortedArray, int key, int low, int high) {
int index = Integer.MAX_VALUE;
while (low <= high) {
int mid = low + ((high - low) / 2);
if (sortedArray[mid] < key) {
low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}
runBinarySearchIteratively方法以sortedArray、key和sortedArray的高、低索引作为参数。当该方法第一次运行时,sortedArray的第一个索引low为0,而sortedArray的最后一个索引high为其长度- 1。
middle是sortedArray的中间索引。现在,算法运行一个while循环,将该键与sortedArray的中间索引的数组值进行比较。
注意中间索引是如何生成的(int mid = low + ((high - low) / 2).这是为了适应非常大的数组。如果只是通过获取中间下标(int mid = (low + high) / 2)生成中间下标,则包含2的30次方或更多元素的数组可能会发生溢出,因为low + high的总和很容易超过最大正int值。
递归实现
下面给出二分的递归实现:
public int runBinarySearchRecursively(int[] sortedArray, int key, int low, int high) {
int middle = low + ((high - low) / 2);
if (high < low) {
return -1;
}
if (key == sortedArray[middle]) {
return middle;
} else if (key < sortedArray[middle]) {
return runBinarySearchRecursively(
sortedArray, key, low, middle - 1);
} else {
return runBinarySearchRecursively(
sortedArray, key, middle + 1, high);
}
}
方法接收sortedArray排序数组、key、sortedArray的低索引和高索引。
Arrays.binarySearch()
int index = Arrays.binarySearch(sortedArray, key);
sortedArray是已排序数组,key是查找内容。
Collections.binarySearch()
int index = Collections.binarySearch(sortedList, key);
Collections的实现结果一样,只不过参数是list类型。
性能比较
采用迭代或递归取决于用户偏好,但两者之间有一些差异需要了解:
- 递归需要维护栈,通常需要更多内存
- 递归在处理大数据集时可能会出现StackOverflowException 异常
- 递归代码更加清晰,而且代码较迭代更简洁
一般情况下,与查找n值较大的线性搜索相比,二分算法执行的比较次数更少。对于n值较小的线性搜索可能比二分搜索执行得更好。当然这种分析是理论性的,也可能会因背景而异。
此外,二分搜索算法需要排序数据集,这也是有代价的,如果使用归并排序算法对数据进行排序,我们的代码就会增加n log n的复杂度。
因此,首先我们需要分析我们的需求,然后决定哪种搜索算法最适。
总结
本文介绍了二分搜索算法的实现,并对比二分搜索、线性搜索两种算法的应用场景。
本文参考链接:https://blog.csdn.net/neweastsun/article/details/123716703