Prove the algorithm given below is correct through Proof of correctness of algorithm (Anything other than a proof will automatically will be down voted!):

The PairSearch algorithm below takes in an array of ordered pairs data and a value x. It returns a value y such that (x, y) appears in data, or it returns nil if x isn't the first element of an ordered pair. Prove that ProductSearch is correct if data contains a single ordered pair where the first element is ax. Hint: if data contains a single ordered pair where the first element is x, then datali] - (x, y) for some integer i, where y is the correct answer. Also, note that the induction hypothesis for this problem will only apply to arrays that contain one pair that starts with r. Input: data: an array of ordered pairs Input: n: the number of ordered pairs in data Input: x: a value to search for Output: value y such that (x, y) E data, or nil if no such pair exists 1 Algorithm: PairSearch 2 if n - 0 thern 3return nil 4 else if data[1] first r then 5return data[11.second 6 else f data[1] first Iterate through data and remove all ordered pairs (a, b) where (a-2)(f-x) 0 9return PairSearch(data, r) 10 end