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)+".");
}
}

}

我想看看二叉搜索需要做的比较数量才能找到这个数字，但我不知道如何实现它。我已经做了一个循环，所以我可以看到比较的平均值，但我不知道如何获得比较的数量。

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) + ".");
}
}

Answer 2

在代码顶部声明一个int，并在每个 return 语句之前递增它(因为这是比较的最后一步)。

int compares = 0;
//other code
compares++;
return blahblah;

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参数传递零。

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将包含调用递归函数的次数。