écrire un algorithme avec Θ (nlogn)

Question

J'ai écrit ce code pour moi (ce n'est pas un travail à domicile) Je veux savoir est-ce correct? Merci

algorithme avec le temps Θ (nlogn), qui peut fournir un tableau de n membres pour déterminer si deux éléments du tableau qui sont égaux à x, puis retournent les éléments

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

Votre recherche binaire est pas juste. Vous ne devriez pas comparer i avec j, vous devriez comparer la somme. En outre, il est plus facile si vous effectuez une recherche binaire pour 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 

Aussi, gardez-vous dans votre m écraser la fonction principale. Vous avez besoin de quelque chose comme ceci:

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] 

Cela vous assure de vous arrêter après avoir trouvé une solution. Dans votre cas, l'algorithme renverra toujours NO_SOLUTION car il n'y a rien à grouper avec le dernier élément. En outre, vous devez seulement aller jusqu'à n - 1 pour la même raison.