CMI2014-B-06a

Question

Let $A$ be an array of $n$ integers, sorted so that $A[1] \leq A[2] \leq \dots \leq A[n]$. You are given a number $x$x. The aim is to find out if there are indices $k$ and $l$ such that $A[k] + A[l] = x$. Design an algorithm for this problem that works in time $O(n)$.

Answer 1