Question

假设我有一个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);
        }            
    }

what is the proper way of calling the method binarySearch(5, a, 0, a.lenght) or binarySearch(5, a, 0, a.lenght-1)

我知道他们都会找到数字,但他们会发现数字的索引不同,从而进行更多的比较

Answer 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



二进制搜索（i，数组，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


As you can see, variances do appear, but the average remains constant.
Now let s test for bigger numbers:

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


Hence, on average it doesn t go either way. For the sake of convention I would advise using the exclusive upper bound version: binarySearch（i，array，0，array.length）

Answer 2

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

Answer 3

可以提出这样的问题:是否包括了权利界限的“强”[低、高]

但在你的函数中，它是[low，high]，a.length-1，正如你看到的low>；高（非低>；=高）和（低，中1）（非（低，中等））。

友情链接