Lower Bound for Sorted 2-Sum
Consider the following problem I'll call check-for-ones (where it is easy to show a lower bound of $\Omega(n)$): given a binary array of length $n$, check if there are any 1s in this array. We'll reduce this problem to the sorted-2-sum problem, thereby showing that sorted-2-sum also should require $\Omega(n)$ time.

We need to be a bit careful what we mean by "reduce" here; the standard notion of polytime reduction is useless, and even a linear-time reduction doesn't say much since we can solve both problems trivially in linear-time. Our reduction will have the following property: it will reduce an instance $y$ of our check-for-ones problem to an instance $x$ of the sorted-2-sum problem such that for any index $i$, we can compute $x_i$ in time $O(1)$ given random access to $y$ (assuming that all word operations take $O(1)$ time). 

Now, if you can solve sorted-2-sum in $O(t)$ time, you read in at most $O(t)$ values $x_i$, and each $x_i$ can be computed from associated $y_j$ in $O(1)$ time, and therefore you can also solve check-for-ones in $O(t)$ time. 

Here is the reduction. Let the array $x$ have length $2n$. When reading a value $x_i$ proceed as follows:


If $1 \leq i\leq n$, let $x_i = -100(n+1-i)$
If $n &lt; i \leq 2n$, let $x_i = 100(i-n) + y_{i-n}$


Now, the equation $x_{j} + x_{k} = 1$ has a solution iff there exists a $y_{i} = 1$ (in particular, $(j,k)$ must be a pair of the form $(n-a, n+a-1)$).

An example might help as well, let $y$ be the following:

$$y = \{0,0,1,0\}$$

We then have that $x$ (if we were to have read $O(n)$ values) would be:

$$x = \{-400, -300, -200, -100, 100, 200, 301, 400\}$$

We can see how $x_j + x_k = 1 \Leftarrow \Rightarrow \exists y_i =1 \in y$. In our case, $-300 + 301 = 1$ implies $y_3 = 1$.