WRITE-UP ONLY, NO NEED FOR A CODE!! Suppose you are given an array A with n entr

Question

WRITE-UP ONLY, NO NEED FOR A CODE!!

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, that is - 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. (So if you were to draw a plot with the array position j on the x-axis and the value of the entry A[j] on the y-axis, the plotted points would rise until x-value p, where they’d achieve their maximum, and then fall from there on.)
You’d like to find the “peak entry” p without having to read the entire array—in fact, by reading as few entries of A as possible. Show how to find the entry p by reading at most O(log n) entries of A. Describe this in your README. Prove that your algorithm works in O(logn). No need to provide code.

Explanation / Answer

Step 1: Let bottom = 1 and top = n

Step 2: If bottom = top, go to step 5

Step 3: Calculate mid = floor((bottom + top)/2)

Step 4: Compare a[mid] with a[mid + 1]
            if (a[mid] > a[mid] + 1) we know that 'peak element' is on the left of mid, hence we set top = mid.
            if (a[mid] < a[mid] + 1) we know that 'peak element' is on the right of mid, hence we set bottom = mid.

Step 5: go to Step 2

Step 6: peak element is a[bottom]
               

The algorithm is very similar to binary search algorithm, where we reduce the search area by half every time, therefore the time complexity is O(log n)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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