I have a problem with O(n * log(n)) searching algorithm.

I have to find two numbers from an array that add up to the given number.

I know how O(n * log(n)) works, but I'm not sure if those two correct numbers will meet in search if I do it like this:

for (int i = 0; i < n; i  )
    for (int j = 1; j <= n; j = j*2)

Is there a way to keep O(n * log(n)) complexity so that every two numbers meet in the search?

CodePudding user response：

1. sort array (O(nlogn))

2. for each element:

   2.1 binary search to find other element that adds up to the given number (or to figure out there is none) (O(logn))

Step 2 has complexity O(nlogn), and so the whole algorithm has O(nlogn)

CodePudding user response：

I have to find two numbers from an array that add up to the given number.

It can be done in O(n) time and utilizing additional O(n) space.

For that, we can index all array elements in a Map. The key of the map would be a difference between the target sum and a particular array element and value - an element itself. Creation of the map requires a single iteration over the source array, i.e. it cost O(n) time.

In the case when the target sum is even and there's only a single array element is exactly equal to the target sum / 2 result would be incorrect. To treat this case, we can count the number of elements that are equal to the half of the sum. It can be done simultaneously with the process of generating the map to avoid performing an additional iteration (although it contradicts clean coding practices).

Then we need to examine whether there's an element in the array that that matches one of the keys contained in the map. If such an element has been found, then we have a pair of numbers that produces the target sum.

So we need to perform only 2 iterations over the source array, and that result to O(n) overall time complexity.