Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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. $$
