Java二分查找算法

在本文中，我们将介绍二进制搜索相对于简单线性搜索的优势，并介绍它在 Java 中的实现。

1. 需要有效的搜索

假设我们在wine-selling业务和数以百万计的买家每天都访问我们的应用程序。

通过我们的应用程序,客户可以过滤掉物品价格低于n美元,从搜索结果中选择一个瓶子,并将它们添加到购物车。我们有成千上万的用户寻求葡萄酒价格限制每一秒。需要快速的结果。

后端,我们的算法运行的线性搜索整个列表葡萄酒比较价格限制输入的客户提供的价格每一个酒瓶在列表中。

然后,它返回物品的价格小于或等于价格限制。这个线性搜索时间复杂度为O (n)。

这意味着我们系统中的酒瓶数量越多，所需的时间就越多。搜索时间与引入的新项目的数量成正比。

如果我们开始按排序顺序保存项目并使用二进制搜索搜索项目，我们可以实现O(log n)的复杂度。

对于二分搜索，搜索结果所花费的时间自然会随着数据集的大小而增加，但不会成比例地增加。

2. 二分查找

简单来说，算法将键值与数组的中间元素进行比较;如果它们不相等，则删除不能包含密钥的一半，并继续搜索剩余的一半，直到成功。

请记住 - 这里的关键方面是数组已经排序。

如果搜索以剩余的一半为空而结束，则该键不在数组中。

(1)迭代实现

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。

中间是sortedArray的中间索引。现在算法运行一个while循环，将键与sortedArray的中间索引的数组值进行比较。

注意中间索引是如何生成的(int mid = low + ((high – low) / 2)。这是为了适应非常大的数组。如果中间索引是通过获取中间索引(int mid = (low + high) / 2) ，包含 2 30 个或更多元素的数组可能会发生溢出，因为low + high的总和很容易超过最大正int值。

(2)递归实现

现在，让我们看看一个简单的递归实现：

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

runBinarySearchRecursively方法接受sortedArray、键、sortedArray的低索引和高索引。

(3)使用数组。二进制搜索()

int index = Arrays.binarySearch(sortedArray, key);

将在整数数组中搜索的 sortedArray和int key作为参数传递给Java Arrays类的binarySearch方法。

(4)使用集合。二进制搜索()

int index = Collections.binarySearch(sortedList, key);

sortedList &整数键,搜索列表中的整数对象,作为参数传递到binarySearch Java集合类的方法。

(5)性能

是否使用递归迭代的方法编写的算法主要是一个个人喜好问题。但仍有一些观点我们应该意识到:

1)慢递归可以维护一个堆栈的开销和通常要占用更多的记忆空间

2)递归不是stack-friendly。它可能导致StackOverflowException当处理大数据集

3)递归添加清晰的代码,使其较短的迭代方法相比

理想情况下,一个二叉搜索将执行更少数量的比较与一个线性搜索大的n, n为较小的值,值的线性搜索可以执行比二进制搜索。

每个人都应该知道这个分析是理论和可能取决于上下文。

此外，二分搜索算法需要一个排序的数据集，它也有它的成本。如果我们使用归并排序算法对数据进行排序，则会在我们的代码中增加n log n的额外复杂度。

所以首先我们需要很好地分析我们的需求，然后决定哪种搜索算法最适合我们的需求。