Java二分查找计算比较次数

Question

我在Java中编写了以下代码，用于二分查找：

import java.util.Arrays;

class BinarySearch  {
    public static int binarySearch(double[] arr, double x, int high, int low)   {
        int mid=(high+low)/2;
        if(high==low || low==mid || high==mid)  {
            return -1;
        }
        if(arr[mid]<x)  {
            return binarySearch(arr, x, high, mid);
        }
        else if(arr[mid]>x) {
            return binarySearch(arr, x, mid, low);
        }
        else if(arr[mid]==x)    {
            return mid;
        }
        return -1;
    }

    public static void main(String args[])  {
        int n=1000;
        double array[] = new double[n];
        for (int i=0; i<100; i++)   {
            for (int k = 0; k < n; k++) {
                double r = Math.random();
                r = r * 100;
                r = Math.round(r);
                r = r / 100;
                array[k] = r;
            }
            Arrays.sort(array);
            double search = Math.random();
            search = search * 100;
            search = Math.round(search);
            search = search / 100;
            int result=binarySearch(array, search, n, 0);
            if (result == -1)
                System.out.println(search +" befindet sich nicht im Array.");
            else
                System.out.println(search+" befindet sich im Array an der Stelle "+(result)+".");
    }
}

我希望能看到二进制搜索需要做多少次比较才能找到数字，但我不知道如何实现。我已经编写了一个循环，以便查看比较的平均值，但我不知道如何获取比较次数。

- user8138142

Answer 1

您可以这样做以保持简单。

private static int comparisions = 0;

public static int binarySearch(double[] arr, double x, int high, int low) {
    int mid = (high + low) / 2;
    if (high == low || low == mid || high == mid) {
        comparisions++;
        return -1;
    }
    if (arr[mid] < x) {
        comparisions++;
        return binarySearch(arr, x, high, mid);
    } else if (arr[mid] > x) {
        comparisions++;
        return binarySearch(arr, x, mid, low);
    } else if (arr[mid] == x) {
        comparisions++;
        return mid;
    }
    return -1;
}

public static void main(String args[]) {
    int n = 1000;
    double array[] = new double[n];
    for (int i = 0; i < 100; i++) {
        for (int k = 0; k < n; k++) {
            double r = Math.random();
            r = r * 100;
            r = Math.round(r);
            r = r / 100;
            array[k] = r;
        }
        Arrays.sort(array);
        double search = Math.random();
        search = search * 100;
        search = Math.round(search);
        search = search / 100;
        int result = binarySearch(array, search, n, 0);
        System.out.println("Number of comparisions " +  comparisions);
        if (result == -1)
            System.out.println(search + " befindet sich nicht im Array.");
        else
            System.out.println(search + " befindet sich im Array an der Stelle " + (result) + ".");
    }

}

- Piyush

Answer 2

在你的代码顶部声明一个int，并在每个返回语句之前递增它（因为这是比较的最后一步）。

int compares = 0;

//other code

compares++;
return blahblah;

- coinbird

Answer 3

你可以将比较次数通过递归方法向下传递，例如：

public static int binarySearch(double[] arr, double x, int high, int low, int cmp) {
    ...
    if(arr[mid]<x)  {
        // We made one additional comparison
        return binarySearch(arr, x, high, mid, cmp+1);
    } else if(arr[mid]>x) {
        // We made two additional comparisons
        return binarySearch(arr, x, mid, low, cmp+2);
    } else {
        // We made two additional comparisons.
        // We are about to return the result, so print the final number of comparisons:
        System.out.println("Performed "+(cmp+2)+" comparisons.");
        return mid;
    }
}

在来自main的调用中，将cmp参数传递为0。

注：本文保留了HTML格式，请注意阅读。

- Sergey Kalinichenko

Answer 4

在 binarysearch() 外声明一个变量

import java.util.Arrays;
   class BinarySearch  {
      int num_of_calls = 0;
      public static int binarySearch(double[] arr, double x, int high, int low)   {
         num_of_calls++;
        ...
        }

num_of_calls 将包含递归函数被调用的次数。

- Cap