# Finding pair of sum in sorted array in time complexity less than $O(n)$

In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $$O(n)$$. If there are other method for finding pairs the sum up to a certain value that is much more efficient.

I was asked this in an interview recently and interviewer told me that there exists a solution with $$O(\log n)$$ time complexity. Any ideas are appreciated.

• Average or worst case? – Andris Birkmanis Dec 17 '20 at 21:01
• He specifically mentioned worst case. How would I do it in O(Log n) in average case. – ABHIJEET SHUKLA Dec 18 '20 at 4:22
• Just to clarify, as I believe the accepted answer is only applicable to disprove the existence of O(log n) worst case. – Andris Birkmanis Dec 19 '20 at 2:34

Suppose that you had an algorithm which gets as input a sorted integer array $$A_1,\ldots,A_n$$, outputs Yes iff $$A_i + A_j = 0$$ for some $$i \neq j$$, and always accesses at most $$n-1$$ inputs.
Suppose first that $$n = 2m$$ is even, and consider the following sorted integer array $$B$$: $$-2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1.$$ This array contains no solution to $$B_i + B_j = 0$$. For any index $$i$$, we can create a sorted integer array $$B^{(k)}$$, differing only in the $$k$$'th entry, which does have a solution to $$B^{(k)}_i + B^{(k)}_j = 0$$.
Now run the given algorithm. Whenever it tries to access a position $$A_i$$, answer the value $$B_i$$. By assumption, the array terminates without querying some position, say $$A_k$$. Therefore the algorithm behaves the same when given as input the arrays $$B$$ and $$B^{(k)}$$, although the answer is No for the first one and Yes for the second one.
When $$n=2m+1$$ is odd, a similar argument works with the following sorted integer array: $$-2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1, 2m+1.$$