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.

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

1 Answer 1


Your interviewer is wrong.

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. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.