二分查找算法的平均性能?

发布于 2024-08-29 20:08:31 字数 568 浏览 6 评论 0原文

如果

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

整数我试图找到总是在数组中,任何人都可以帮我编写一个可以计算二分搜索算法的平均性能的程序吗?

编辑:我知道我可以通过实际运行程序并计算调用次数来完成此操作,但我在这里尝试做的是在不调用函数的情况下完成此操作。

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

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: 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)

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

小忆控 2024-09-05 20:08:31

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

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

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文