分而治之：IndexSearch

給一個算法來找到一個索引i，使得1 < = I < = n和A [I] = 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）在這種情況下？

我假定：

2T（N/2）+ O（1）---->是不是能否詳細解釋我如何解決應用主定理的復發？

a = 2的B = 2 F（N）= 1 N^logba = N ---> N隨1所以我們有情況1導致爲O（n） - > ????對？

來源

2013-02-15 Patric

這當然是不正確的。

由於您忽略了遞歸調用的返回值，因此如果不是這種情況，您的程序在第一次調用時確實只會檢查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 
}

而且這是一個非常明確的解決方案，所以也許這就是要優於更復雜的一個。

我很抱歉，我不能幫你與你的其他問題。

編輯：這應該工作。它是用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

希望有所幫助。

編輯：查找所有出現實際上導致一個好得多的解決方案：

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]

我認爲這是件很好，純粹的解決方案;-)

來源

2013-02-16 21:50:49

我的目標是儘量使用分而治之的辦法來解決這個問題.... – Patric 2013-02-17 09:41:22

感謝ü烏拉圭回合的努力！它適用於你有1個元素等於索引的情況，但是如果我想打印所有具有相同數組索引的元素呢？嘗試l = [1,2,3,3,4,6,7,8,9] ...它只會打印一個元素。 – Patric 2013-02-17 18:20:32

看看我上面的可能解決方案... – Patric 2013-02-17 18:29:15

我想這將是一個可能的解決方案，我打印出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;

}

來源

2013-02-17 18:28:32 Patric

分而治之：IndexSearch

回答

相關問題