algorithm - 用 Θ(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

此外，您不断在 main 函数中覆盖 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。