Разделяй и властвуй: IndexSearch

Question

я решил следующую задачу себе:

Дайте алгоритм, чтобы найти индекс я, что 1 < = я < = п и А [I] = я обеспечить такой индекс существует. Если есть такие индексы, алгоритм может вернуть любой из них.

Я использовал разделяй и властвуй подход и как результат я получаю:

public static int IndexSearch(int []A, int l, int r) { 
    if (l>r) 
    return -1; 
    int m = (l+r)/2; 
    IndexSearch(A, l, m-1); 
    IndexSearch(A, m+1, r); 
    if (A[m]==m) 
    return m; 
    else 
    return -1; 
} 

Сначала хотел спросить, если это правильно? Я думаю, да ....

Что такое рекурсия T (n) в этом случае?

Я полагаю:

2Т (п/2) + O (1) ----> правильно ли это? можете ли я подробно объяснить мне, как решить повторение, применяя магистерскую теорему?

a = 2 b = 2 f (n) = 1 n^logba = n ---> n vs 1, поэтому мы имеем CASE 1, что приводит к O (n) -> ???? правильно?

Answer 1

Это, безусловно, неверно.

Поскольку вы игнорируете возвращаемые значения ваших рекурсивных вызовов, ваша программа действительно проверяет только A[m] == m в вашем самом первом вызове и возвращает -1, если это не так.

«очевидное» решение было бы что-то вроде:

public static int IndexSearch(int []A, int l, int r) { 
    for i in range(1, length(A)) 
    if (A[i] == i) 
     return i 
    return -1 
} 

Кроме того, это очень прозрачный раствор, поэтому, возможно, это будет предпочтительнее более изощренный.

Прошу прощения, я не могу помочь вам с вашими другими вопросами.

EDIT: Это должно работать. Он написан на Python, но его должно быть достаточно легко понять. Вопрос о разделении и покорении заключается в том, чтобы уменьшить проблему до точки, где решение очевидно. В нашем случае это будет список только с одним элементом. Единственная трудность здесь заключается в возврате возвращаемых значений.

def index(l, a, b): 
    if a == b: #The basecase, we consider a list with only one element 
     if l[a] == a: 
      return a 
     else: return -1 

    #Here we actually break up 
    m = (a+b)/2 

    i1 = index(l, a, m) 
    if i1 != -1: 
     return i1 

    i2 = index(l, m+1, b) 
    if i2 != -1: 
     return i2 

    return -1 

Вот пример вывода:

l = [1,2,3,3,5,6,7,8,9] 
print index(l, 0, len(l)-1) 

Output: 3 

Надежда, что помогает.

EDIT: Поиск всех вхождений на самом деле приводит к гораздо приятнее решение:

def index(l, a, b):  
    if a == b: 
     if l[a] == a: 
      return [a] 
     else: 
      return [] 

    m = (a+b)/2 
    return index(l, a, m) + index(l, m+1, b) 

который имеет в выводе:

l = [1,2,3,3,5,6,7,8,8] 
print "Found " , index(l, 0, len(l)-1), " in " , l 

Found [3, 8] in [1, 2, 3, 3, 5, 6, 7, 8, 8] 

и

l = range(0,5) 
print "Found " , index(l, 0, len(l)-1), " in " , l 

Found [0, 1, 2, 3, 4] in [0, 1, 2, 3, 4] 

Я думаю, что делает для хорошее, чистое решение ;-)

Answer 2

Я предполагаю, что это было бы возможным решением, когда я распечатаю все возможные элементы, где value = index.

public static int IndexSearch(int []A, int l, int r) { 

if (l>r) 
    return -1; 


//Divide into subproblems 
int m = (l+r)/2; 

//Conquer and find solution to subproblems recursively 
IndexSearch(A, l, m-1); 
IndexSearch(A, m+1, r); 

//Combine solutions of subproblems to the orignal solution of the problem 
if (A[m]==m) 
    System.out.println(m); 

return 1; 

}