0

http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance

BinarySearch(int A[], int value, int low, int high)
{
    int mid;
    if (high < low)
        return -1;
    mid = (low + high) / 2;
    if (A[mid] > value)
        return BinarySearch(A, value, low, mid-1);
    else if (A[mid] < value)
        return BinarySearch(A, value, mid+1, high);
    else
        return mid;
}

如果我要查找的整数始终在数组中,有人可以帮我编写一个可以计算二进制搜索算法平均性能的程序吗?

编辑:我知道我可以通过实际运行程序并计算调用次数来做到这一点,但我在这里要做的是在不调用函数的情况下做到这一点。

编辑2:KennyTM:这是一个时间复杂度,我正在尝试计算平均调用次数。例如,在 A[2] 中查找整数的平均调用次数为 1.67 (5/3)

4

1 回答 1

0

您不需要“程序”。您可以只计算对该方法的调用次数BinarySearch

您可以通过传递另一个参数(通过指针)或使用全局变量轻松地做到这一点。在这种情况下 - 它是一个玩具 - 所以我可能会快速而肮脏地使用全局。

于 2010-04-25T16:58:16.537 回答