Skip to main content
 首页 » 编程设计

Java二分搜索算法实现教程

2022年07月19日144三少

本文解释基于线性结构的二分查找算法,并给出几种实现的代码示例。

需求场景

假设电商系统中,每天大量用户访问产品页面,用户可以设置低于一定价格的条件过滤产品,并从过滤结果中选择商品加入购物车。因每秒同时有大量用户通过设置价格上限过滤产品,结果展示需要非常块。

后端在产品列表采用线性搜索算法与用户输入价格进行比较,然后返回符合条件的产品。这样时间复杂度为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
阅读延展