0

假设我有一个 10 个整数的数组，并且我正在使用二进制搜索来查找一个数字，让我们以数字为例

1 2 3 4 5 6 7 8 9 10

我正在使用这种方法

static void binarySearch(int n, int[] a, int low, int high)
    {
        int mid = (high + low) / 2;
        if(low > high)
            System.out.println(n+" was not found after "+counter+" comparisons");
        else if(a[mid] == n)
        {
            counter++;
            System.out.println(n+" was found at position "+mid+" after "+counter+" comparisons");
        }            
        else if(a[mid] < n)
        {
            counter++;
            binarySearch(n, a, mid+1, high);
        }            
        else
        {
            counter++;
            binarySearch(n, a, low, mid-1);
        }            
    }

调用方法 binarySearch(5, a, 0, a.lenght) 或 binarySearch(5, a, 0, a.lenght-1) 的正确方法是什么

我知道他们都会找到这个数字，但他们会在不同的索引处找到它；从而进行更多的比较

4

3 回答 3

2

正确的方法是避免这种方法，并使用标准的Arrays.binarySearch()方法，该方法具有被记录的巨大优势，以及返回结果而不是在 System.out 上打印结果的另一个巨大优势（这使得它无用）。

于 2012-05-27T17:11:57.607 回答
1

好吧，让我们做一些测试好吗？

首先，让我们搜索数组中的每个数字。我们得到：

binarySearch(i, array, 0, array.length);

1 was found at position 0 after 3 comparisons
2 was found at position 1 after 4 comparisons
3 was found at position 2 after 2 comparisons
4 was found at position 3 after 3 comparisons
5 was found at position 4 after 4 comparisons
6 was found at position 5 after 1 comparisons
7 was found at position 6 after 3 comparisons
8 was found at position 7 after 4 comparisons
9 was found at position 8 after 2 comparisons
10 was found at position 9 after 3 comparisons
Average: 2.9 comparisons

binarySearch(i, array, 0, array.length - 1);

1 was found at position 0 after 3 comparisons
2 was found at position 1 after 2 comparisons
3 was found at position 2 after 3 comparisons
4 was found at position 3 after 4 comparisons
5 was found at position 4 after 1 comparisons
6 was found at position 5 after 3 comparisons
7 was found at position 6 after 4 comparisons
8 was found at position 7 after 2 comparisons
9 was found at position 8 after 3 comparisons
10 was found at position 9 after 4 comparisons
Average: 2.9 comparisons

如您所见，确实会出现差异，但平均值保持不变。现在让我们测试更大的数字：

100000 items
binarySearch(i, array, 0, array.length);
Average: 15.68946 comparisons
binarySearch(i, array, 0, array.length - 1);
Average: 15.68946 comparisons

200000 items
binarySearch(i, array, 0, array.length);
Average: 16.689375 comparisons
binarySearch(i, array, 0, array.length - 1);
Average: 16.689375 comparisons

500000 items
binarySearch(i, array, 0, array.length);
Average: 17.951464 comparisons
binarySearch(i, array, 0, array.length - 1);
Average: 17.951464 comparisons

因此，平均而言，它不会走任何一条路。为了约定，我建议使用独占上限版本：binarySearch(i, array, 0, array.length);

于 2012-05-27T17:12:51.373 回答
0

问题可以表述为：边界是右包含的[low, high]还是右排除的[low, high)？右排他形式具有由 Dijkstra“创立”的悠久计算机科学传统。在我看来，它也更优雅一些（a.length 而不是 a.length-1）。

但是在您的函数中，它是 [low, high], a.length-1，因为您看到 low > high（不是 low >= high）和（low，mid-1）（不是（low，mid））。

于 2012-05-27T17:28:52.527 回答