Given a sorted array of integers and a target integer, find a pair of integers in the array that sum to the target in linear time.

find-the-two-numbers-in-a-sorted-array-which-sum-up-to-given-number.py

#!/usr/bin/env python

# http://www.disinformatics.com/blog/2010/12/14/a-google-internship-interview-question-in-scala/

# The question is: 
# given a sorted array of integers and a target integer, 
# find a pair of integers in the array that sum to the target in linear time.

# The Solution
# 
# A solution is to initialise two pointers to the ends of the array and
# compute the sum of the two elements pointed to. If the sum equals the
# target, we’re done.
# 
# If not, it either exceeds the target (in which case we can decrease our
# candidate solution by the smallest amount possible in a unique way:
# decrementing the upper pointer) or is too small (in which case we perform
# the dual operation and increment the lower pointer).
# 
# We repeat this process (via a while loop or recursion) until we find a
# solution or the pointers cross (if they cross, there was no pair of distinct
# elements of the array that summed to the target).
# 
# It’s linear time because on each pass of the loop/recursion, the algorithm
# either terminates (by success or pointers crossing) or the distance between
# the pointers decreases by one. Therefore in the worst case (i.e. termination
# as late as possible), the pointers meet and force termination – they must
# have jointly travelled n places, where n is the length of the array.
# Therefore it’s O(n) – linear time.

# in python ...

import random

a = sorted([ random.randint(0, 100) for x in range(100) ])
target = sum(random.sample(a, 2))

right = len(a) - 1
left = 0

counter = 0

while not a[left] + a[right] == target:
    if a[left] + a[right] > target:
        right -= 1
    else:
        left += 1
    counter += 1

print 'counter/len(a):', counter, len(a)
print 'target:', target
print 'index  left/right: %s/%s' % (left, right)
print 'values left/right: %s/%s' % (a[left], a[right])