二进制搜索算法的平均性能？ [英] Average performance of binary search algorithm?

问题描述

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;
}

如果整我想找到的是始终在数组中，任何人都可以帮我写一个程序，可以计算二进制搜索算法的平均性能？

If the integer I'm trying to find is always in the array, can anyone help me write a program that can calculate the average performance of binary search algorithm?

编辑：我知道我可以通过实际运行程序和计算呼叫的次数做到这一点，但我想要做的，是做不调用函数

edit: I know I can do this by actually running the program and counting the number of calls, but what I'm trying to do here is to do it without calling the function.

EDIT2：KennyTM：这是一个时间复杂度，我试图计算呼叫的平均数量。例如，呼叫的平均数量来查找A中的整数[2]，这将是1.67（5/3）

edit2: KennyTM: That is a time complexity, I'm trying to calculate the average number of calls. For example, the average number of calls to find a integer in A[2], it would be 1.67 (5/3)

推荐答案

您并不需要一个节目。你可以仅仅指望调用二分查找方法的数目。

You don't need a "program". You can just count the number of calls to the BinarySearch method.

您可以做到这一点很容易地通过传递另一个参数（通过指针），或使用全局变量。在这种情况下 - 这是一个玩具 - 所以我可能会去快速和肮脏与全球

You can do that easily by passing another parameter (by pointer) or using a global variable. In this case - it's a toy - so I'd probably go quick and dirty with the global.

这篇关于二进制搜索算法的平均性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！