Поиск эффективности поиска? алгоритм. C++

Question

Мне сказали, чтобы найти эффективность этого кода, и мы уже ~ 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() E.J .: O (1), O (n^2) ...)

Answer 1

Это в основном ternary search. v должен быть отсортированным массивом, x - это значение, которое было найдено, и b ist начало диапазона, а a является конечным (эксклюзивным).

Функция пытается разделить диапазон на три относительно равных разделов на m1, m2 (которые оба рассчитаны неправильно и работают только при поиске первого элемента) и проверяет, лежит ли x на границах. Если нет, то рекурсивно с разбиением х должен лежать в.

Код может быть исправлено с

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

Затем, эффективность должна быть O (журнал N)