Finding a Sum in an Array

An algorithm

Problem Statement: Given an increasingly sorted array and a number s, please find two numbers whose sum is s. If there are multiple pairs with sum s, just output any one of them. For example, if the inputs are an array [1, 2, 4, 7,11, 15] and a number 15, output two numbers 4 and 11 since 4+11=15.

Assume the requested value will always be possible to attain.

Analysis: The most brute force way to solve this is to compare each element one at a time against every other element until we reach the value we requested. While this approach has a space complexity of O(1), the time complexity is O(n^2).

Moreover, this solution doesn't take advantage of the array being sorted.

Solution: A better approach is to start your comparison at the two outer elements of the array. In the example given, point two cursors at 1 and 15. If the sum of these two numbers is too high, move the right most cursor inward; the new sum will be smaller. If the sum is too low, move the left cursor inward; the new sum will be higher.

def sum_in_array(arr, sum)
  left_index = 0
  right_index = arr.length - 1
  while arr[left_index] + arr[right_index] != sum
    left_index += 1 if arr[left_index] + arr[right_index] < sum
    right_index -= 1 if arr[left_index] + arr[right_index] >sum
  end
  [arr[left_index], arr[right_index]]
end

With this approach, time complexity is O(n) and space complexity is O(1).

Can you think of any improvements? I can think of a few changes, but do the changes modify the overall O(n)?

Happy coding.