TwoSum

Description of Problem

Given a list of integers and a target, find two integers that sum to the target.

Walking inward algorithm

TwoSum: Scans sorted list, values, for two entries that sum to target.

If values.length < 2 then return []
Calculate sum = values.smallest + values.largest.
If sum > target then we deduce that if the largest number added to the smallest number is greater than the target then the largest number added to any other number on the list will also be greater than the target. Remove values.largest from values and goto 1.
If sum < target then we deduce that if the smallest number added to the largest number is less than the target then the smallest number added to any other number on the list will also be less than the target. Remove values.smallest from values and goto 1.
If sum = target then return [values.smallest, values.largest].

Example

Input: [0, 2, 11, 19, 90], 21

↓				↓
0	2	11	19	90

Sum smallest and largest remaining values: 0 + 90 > 21

If 90 is greater than 21 when added to the smallest number, 0, then we can conclude that 90 is also greater than 21 when added to any number in the list, and therefore eliminate 90 as belonging to a valid solution.

↓			↓
0	2	11	19	90

Sum smallest and largest remaining values: 0 + 19 < 21

If 0 is less than 21 when added to the largest remaining number, 19, then we can conclude that 0 is also less than 21 when added to any number in the list, and therefore can eliminate 0 as belonging to a valid solution.

	↓		↓
0	2	11	19	90

Sum smallest and largest remaining values: 2 + 19 = 21

Valid solution found.

VB.NET

Function TwoSum(values As List(Of Integer), target As Integer) As Integer()

    Dim A As Integer = 0
    Dim B As Integer = values.Count - 1

    Do
        If A >= B Then Return New Integer() {}

        ' Mmmm.. dim sum.
        Dim sum As Integer = values(A) + values(B)

        If sum > target Then
            B -= 1
        ElseIf sum < target Then
            A += 1
        Else
            Return New Integer() {values(A), values(B)}
        End If

    Loop

End Function