Difference between revisions of "TADM2E 4.2"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
(No difference)

Revision as of 18:14, 11 September 2014

(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.