Consider the following problem.

Given: A sorted array A of integers and an integer T.

Goal: Determine if there exist two integers in A (possibly the same integer) whose sum equals T. Now consider the following algorithm for the above problem.

Input: Sorted array A of integers, integer T.

Output: true if there exist two integers in A (possibly the same integer) whose sum equals T; false otherwise.

Code:

left = 0

right = A.length 1

while left T then <= right do

x = A[left] + A[right]

if x == T then

return true

if x < T then

left++

if x > T then

right--

return false

Show that the above algorithm is correct by proving the following statement:

At the start of the ith iteration the following conditions hold:

left right

If there exist indices i and j such that A[i] + A[j] equals T, then left i j right.