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

Question

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)$?

Answer 1

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

This is only possible if the array is sorted.

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?