Let a[0 . . . n] be an array of n + 1 natural numbers not exceeding n. let k < n be an integer such that the values of any tw
o successive entries of a differ at most by k, i.e., |a[j] − a[j + 1]| ≤ k for all j ∈ {0, . . . , n − 1}. 1. prove that there exist an index j such that |a[j] − j| ≤ (k + 1)/2. 2. given the number k, find an o(log n) divide and conquer algorithm that finds such an index.
