找到搜索的效率？算法。C++

Question

我被告知要找到这段代码的效率，我们花了一个小时(我和我的合作伙伴)试图找出这段代码到底能做什么。

我们认为这是一种搜索算法，但我们无法真正找到一种方法使其工作，使其进入无限循环：

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()表示法E.J.：O(1)，O(n^2).)

Answer 1

基本上是三元搜索。v必须是一个排序数组，x是搜索的值，b是范围的开始，a是结束(排他的)。

该函数试图将m1、m2上的等号分区划分为三个(这两个分区计算都是错误的，只有在搜索第一个元素时才能工作)，并检查x是否位于边界上。如果不是的话，它会递归到分区x中。

代码可以用

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

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