def sumMatch(A, n, val):
'''A: list of at least n increasing integers, n > 0.
Return true if there are indices i and j such that A[i] + A[j] == val;
return false otherwise. Examples:
If A contains -3, 1, 2, 5, 7, then sumMatch(A, 5, 6) is true (1+5 is 6),
sumMatch(A, 5, 14) is true, and sumMatch(A, 5, 12) is true,
but sumMatch(A, 5, 11) and sumMatch(A, 5, 0) are both false.
The O(1) loop body eliminates one index in 0..n-1 each time,
so whole loop and algorithm is O(n).
'''
i = 0 # smallest possible i and the largest possible j,
j = n-1 # so a currently true statement which will be a loop invariant is:
# The value of i cannot be lower; the value of j cannot be higher.
while i <= j: # can assume i<=j
if A[i] + A[j] == val:
return True
if A[i] + A[j] < val: # A[i] + A[k] < val for all k <=j,
# already completely eliminated k > j, by loop invariant
# so i works with nothing: completely eliminate it;
# already no k < i by loop invariant, so now no k <= i
i += 1 # if increment i, all k < new i are eliminated
else: # A[i] + A[k] > val for all k >= j ...
j -= 1 # same idea for argument so reduced j satisfies invariant
# invariant maintained: i cannot be lower; j cannot be higher
return False # no options left, since we can assume i is the lower index
N = [-3, 1, 2, 5, 7]
print ('N =', N)
for (n, val) in [(5, 6), (5, 12), (5, 14), (4, 2), (4, 1), (5, 5), (5, 0)]:
print("sumMatch(N, {}, {}): {}".format(n, val, sumMatch(N, n, val)))