搜索數組

Question

我有一個數組int x []和一個數字。我喜歡在數組上進行搜索，使x [i] + x [i + 1] =數字。

什麼是Java中最高效和最快捷的方式？

Answer 1

這是一個僞代碼，這應該工作。只有n個內存讀取。

buff1 = x[0] 
buff2 = 0 
for i = 1 to n - 1 
    buff2 = x[i] 
    if (buff1 + buff2) == number 
     then 
     MATCH 
    endif 
    buff1 = buff2 
endfor 

Answer 2

如果數組未經排序且您只進行少量搜索，則使用phoxis的方法。預計運行在O（n * k）中，其中n是x的大小，k是您想要創建的搜索數量。

如果對數組排序，我們知道x [i] < = number/2且x [i + 1]> = number/2。使用binary search找到（最後一個）前輩編號/ 2 + 1，並檢查是否匹配。

int i = binaryPredecessor(x , number/2 + 1); 
if(x[i] + x[i+1] == number){ 
    return i; 
} 
else if(x[i-1] + x[i] == number){ 
    //The case where x[i] == number/2, and we found the last of two occurrences 
    return i-1; 
} else { 
    //No match exists 
    return -1; 
} 

運行時間爲O（log（n）* k）。

如果您進行了大量搜索，則可能需要對數組進行排序，並使用上述方法。該數組可以按O（n * log（n））排序[見mergersort]。所以如果你想做更多的log（n）搜索，那麼排序數組是值得的。 （如果k接近log（n），做一些測試，看什麼最好:)）