Check for each possible k, whether it is the maximum element by checking adjacent values i.e. a[k-1], a[k] and a[k+1] circularly (meaning, for k=0, check a[n-1], a[0] and a[1]). This is obviously O(n) due to k's range and because 3 comparisons per k can be considered as O(1) being constant time access to array elements. Thus, of course we aim at sub linear time.
So the main issue is - how to reduce problem size so that we solve smaller and smaller problems, discarding some part of the input and get quickly to the problem of size small enough (ideally 1). What if we have the middle element, i.e. a[m]? In order to decide which part to discard, one must be able to visualize the rotated sorted array, which is shown as follows. Let the new index of maximum element be k.
Now, one can see that m will always lie on upward slope and thus slope trick will not work. But, we can now distinguish between left and right part around k as follows. If m<=k, m will always be more than the first element in the rotated array, because the sorted order is retained. Thus, by comparing a[m] and a[i], one can easily decide which part to throw. If a[m] >= a[i] we can throw left half else right half. Once we reduce problem size to 1, m and k collide. This works in O(log n).
No comments:
Post a Comment