By writing an algorithm with Θ (nlogn)

Question

I wrote this code for myself (this is not homework), I want to know is it right? thanks

An algorithm over time Θ (nlogn), which can provide an array of n elements to determine if two elements in the array are equal to x, and then return those elements

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[ij],j+1,q) // end of BinarySearch algorithm 

Answer 1

Your binary search is wrong.

You should not compare i with j , you should compare the sum. It is also easier if you perform a binary search of 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 

In addition, you save the rewriting of m in your main function. You need something like this:

 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] 

This ensures that you stop after finding a solution. In your case, the algorithm will always return NO_SOLUTION , because there is nothing to group the last element. Also, for the same reason, you only need to go up to n - 1 .