Walking in from both ends

One pointer goes at the start of the list and one at the end, and they walk toward each other. Only one moves at each step; you decide which by looking at where things stand.

1lo, hi = 0, len(values) - 1
2while lo < hi:
3    total = values[lo] + values[hi]
4    if total == key:
5        return True
6    if total < key:
7        lo += 1
8    else:
9        hi -= 1
10return False

Because the list is sorted: if the sum is too small, the only way to make it bigger is to move the left one right; if too big, the right one left. Each step rules one element out for good, so it ends in n steps.

A palindrome check is the same walk: are the elements at the two ends equal, and if so both step in. When they meet in the middle, it is done.

Tasks