def sumMatch(A, n, val):
'''A: list of at least n strictly 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 loop eliminates one index in 0..n-1 each time, so it 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: # since j can't be higher, i must be
i += 1
else: # A[i] + A[j] > val # since i can't be smaller, j must be
j -= 1
# 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)))