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. Below is the Algorithm.

1 left = 0

2 right = A.length1

3 while left <= right do

4 x = A[left] + A[right]

5 if x == T then 6 return true

7 if x < T then

8 left + +

9 if x > T then

10 right

11 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: 2 left right

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

Please use proofs to solve this and also use loop invarients