寫有Θ（nlogn）的算法

Question

我寫我自己的代碼（它不是一個在家工作），我想知道這是正確的？謝謝

算法的時間Θ（nlogn），它可以提供n個成員的數組，以確定數組中的兩個元素是否等於x，然後返回這些元素

Algorithm Sum(arr,1,n): 
MergeSort(arr) 
For i<-- 1 to n 
    m<-- BinarySearch(arr,arr[i],i+1,n) 
return m and arr[i] 
//end of the sum algorithm 

Algorithm BinarySearch(arr,arr[i],p,q) 
J<--[p+q/2] 
If (arr[j]+arr[i]=x) 
     Return arr[j] 
else if (i<j) 
     Return BinarySearch(arr,arr[i],p,j-1) 
else 
     Return BinarySearch(arr,arr[i-j],j+1,q) 
// end of BinarySearch algorithm 

Answer 1

您的二分查找不正確。

你不應該比較i與j，你應該比較總和。此外，如果您對二進制搜索x - arr[i]更容易。

Algorithm BinarySearch(arr,arr[i],p,q) 
if (p == q) 
    if (arr[p] == x - arr[i]) 
     return p 
    else 
     return NO_SOLUTION 
j<--[(p+q)/2] // you forgot parentheses 
If (arr[j] = x - arr[i]) 
     Return arr[j] 
else if (arr[j] > x - arr[i]) // our number is too big, restrict the search to smaller numbers 
     Return BinarySearch(arr,arr[i],p,j) 
else 
     Return BinarySearch(arr,arr[i],j+1,q) // arr[i] doesn't change 

此外，您在主函數中一直覆蓋m。你需要的東西是這樣的：

Algorithm Sum(arr,1,n): 
MergeSort(arr) 
m = NO_SOLUTION 
For i<-- 1 to n - 1 
    if (m = NO_SOLUTION) 
     m<-- BinarySearch(arr,arr[i],i+1,n) 
    else 
     break; 

if (m = NO_SOLUTION) 
    return NO_SOLUTION 
else 
    return m and arr[i] 

這可以確保你停止你找到了解決辦法之後。在你的情況下，該算法總是會返回NO_SOLUTION，因爲沒有什麼可以將最後一個元素分組。此外，出於同樣的原因，您只需要升至n - 1。