1

我被告知要找出这段代码的效率，我们花了大约 1 个小时（我和我的伙伴）试图找出这段代码的真正作用。

我们认为这是一种搜索算法，但我们真的找不到一种方法让它在不进入无限循环的情况下工作：

int busq(int *v, int x, int b, int a){
    int m1, m2;
    int result;
    m1 = (b+a) / 3;
    m2 = 2*m1;

    if (v[m1] == x)
         result = m1;
    else
        if (v[m2] == x)
            result = m2;
        else
            if (x<v[m1])
                result = busq(v, x, b, m1-1);
            else
                if (x>v[m2])
                    result = busq(v, x, m2+1, a);
                else
                    result = busq(v, x, m1+1, m2-1);
    return result;
}

这就是我们得到的全部内容，参数 a、b 或 x 没有值，*v （向量）的大小或向量的内容也没有。

应该可以这样解决。

如果我们想知道这段代码的作用，但如果您能告诉我们效率，我们也将不胜感激。（我们使用 O() 表示法 EJ：O(1), O(n^2)...）

4

1 回答 1

3

它基本上是三元搜索。 v必须是一个排序数组，x是搜索的值，是b范围的开始，a是结束（不包括）。

该函数尝试在 处将范围分成三个大约相等的分区m1（m2这两个分区都计算错误，并且仅在您搜索第一个元素时才有效）并检查 x 是否位于边界上。如果不是，它会使用 x 必须位于的分区进行递归。

代码可以用

m1=b+(a-b)/3;
m2=b+(a-b)*2/3;

那么，效率应该是 O(log n)

于 2013-10-04T20:37:31.760 回答