# Design an optimal algorithm that finds 2 array indices in a sorted array such that $A [i] + A [j] = k$

Text:

Given a non-descending ordered array A and an integer k, design an algorithm to find,
if any, the indices of a pair of elements whose sum is equal to k.
Discuss the complexity and the optimality of the solution.
Example
Input: 1, 3, 4, 5, 7  k=7  Output: 2,3 because A[2] + A[3] = 7


I tried to write the easiest algorithm to solve the problem and then try to improve it as much as possible,

Here's my first try:

function searchpair(A, k) : int
{
for i <- 0 to length(A) do
for j <- 0 to length(A) do
if(A[i]+A[j] == k) do
return (i,j)
end
end
}


The complexity of this algorithm is clearly $$O(n^2)$$, and it's not a good result, so I thought it was not necessary to check for elements larger than k (unless there are negative elements as well), and in this case, I transformed the previous algorithm into this:

function searchpair(A, k) : int
{
n = length(A)
while(A[n] > k) do
n = n-1
for i <- 0 to n do
for j <- 0 to n do
if(A[i]+A[j] == k) do
return (i,j)
end
end
}


Depending on the array I could save a lot of operations, but the complexity is still an $$O (n ^ 2)$$. I've thought about applying a divide-and-conquer approach, but I can't think of any way to apply it, for example:

taking the array of the example: 1, 3, 4, 5, 7, and k = 7 A divide-and-conquer algorithm works

1) 1, 3, 4
1) 1,3 NO
2) 3,4  --> FOUND
2) 4, 5, 7
1) 4, 5 NO
2) 5, 7 NO


but assuming that k = 6, this approach doesn't work anymore, is it possible to obtain an algorithm of complexity less than $$O (n ^ 2)$$?

Given $$i$$, you could find an index $$j$$ verifying $$i \leqslant j < n$$ such that $$A[i] + A[j] = k$$ using a binary search. This would result in a total complexity $$\mathcal{O}(n\log n)$$.
Note that it can even be done in linear time, with one index working from the left and one from the right. For $$k=0$$, with negative numbers allowed, this solution was given here: How to develop an O(N) algorithm solve the 2-sum problem?