написание алгоритма с помощью Θ (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 по той же причине.