TADM2E 4.2
From Algorithm Wiki
(a) Check the first 3 integers in the array, and get rid of the middle one. Repeat this with the next integer from the array and continue until we are left with the desired pair of integers, leading to an algorithm that runs in O(n) worst-case time.
(b) The answer is straight forward: S[1] and S[n], since they are the two extreme values.
(c) Sort the array with any nLog(n) method. Then scan through the sorted array to find the smallest gap, thus the desired pair.
(d) Same as above.
