Suppose you are given an array A with n entries, with each entry holding a disti

Question

Suppose you are given an array A with n entries, with each entry holding a distinct number. You are told that the sequence of values A[1], A[2], …, A[n] is unimodal: for some index p between 1 and n, the values in the array entries increase up to position p in A and then decrease the remainder of the way until position n. For example, the array A = [1 3 4 5 6 7 8 5 2] is unimodal, with the entries increasing up to position A[7] = 8 and decreasing afterwards. Implement an algorithm (in C++ or Java) that finds the “peak entry” p without having to read the entire array. Your algorithm should run in O(logn).

Explanation / Answer

The algorithm has to look at A[n/2 1],A[n/2],A[n/2 + 1] in order to find if n/2 is on the increase, decerase, or is the at it’s peak.

If on the increase, recurse on indices n/2 + 1...n, and

if on the decrease, recurse on indices 1... n/2 1.

Therefore the number of accesses of A is bounded by the recurrence T(n) T(n/2)+3 for n 4and T(3) 3.

By s0ubstituting T(n) = 3log2 n3log2(3/2)

It solves the recurrence

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.