是否可以计算递归二分查找的比较次数?如果是这样,怎么办?
这是我所指的搜索:
//binary search
public static int binarySearch(int[] items, int start, int end, int goal)
{
if (start > end)
return (-1);
else
{
int mid = (start + end)/2;
if (goal == items[mid])
return (mid);
else
if (goal < items[mid])
return (binarySearch(items, start, mid - 1, goal));
else
return (binarySearch(items, mid + 1, end, goal));
}
}//end binarySearch
最佳答案
在方法外部声明计数变量。然后每次调用该方法时加 1。
long count = 0;
//binary search
public static int binarySearch(int[] items, int start, int end, int goal)
{
count += 1
if (start > end)
return (-1);
else
{
int mid = (start + end)/2;
if (goal == items[mid])
return (mid);
else
if (goal < items[mid])
return (binarySearch(items, start, mid - 1, goal));
else
return (binarySearch(items, mid + 1, end, goal));
}
}//end binarySearch
关于java - 二分查找的比较次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23463784/