2. Suppose that you are given an unsorted array A of length n, in which all valu

Question

2. Suppose that you are given an unsorted array A of length n, in which all values are different re that A[i] A[i + 1] and Ali] Ali-1] ( f A. then it need only be less than the single adjacent element). In other words, Ali] is less than all adjacent values in A al numbers. A local manamum of A 1s an index 2 such If i îs the first or last element Create an efficient algorithm for finding a local minimum in better than O(n) time. Note that you don't need to return all local minima- just one (Hint: Suppose you split the array in half, and compare the two boundary elements Aljl and Alj + 11. If Aljl Alj + 11. on which side are you quar- anteed to find a local minimum? What if A[j + 1]ADI? Why?) What is the running time of your algorithm?

Explanation / Answer

Hi,

The algorithm to your question is

Check if ((m == 0 || a[m-1] > a[m]) &&(m == n-1 || a[m+1] > a[m]))

return m

EndIf

Check if (m > 0 && a[m-1] < a[m])

return localmin(a, l, (m -1), n)

EndIf

return localmin(a, (m+ 1), h, n)

EndFunction

Run the above function as localmin(a, 0, n-1, n)

The above algorithm takes time of O(logn)

Revert in case of any queries

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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