6. You are presented with a row of n face-down cards that have distinct, unknown
ID: 3144482 • Letter: 6
Question
6. You are presented with a row of n face-down cards that have distinct, unknown numbers on their faces; to read the number on a card, you must flip it over. We say that a card is a local minimum if its number is smaller than those of its two immediate neighbors (or its one neighbor, if it is at an end of the row). Using the divide-and-conquer paradigm, design an algorithm that finds a local minimum by flipping over just O(log n) cards. Prove that your algorithm is correct and flips the claimed number of cards. (Note that there may be multiple local minima; your algorithm just needs to find onc of them.)Explanation / Answer
Hi,
We can use binary search technique to solve this,
1. First we will look at first and last element, if either of them is min then we return it
2. otherwise, flip the middle element, now there are 3cases
a. middle card is min, if yes we are done
b. middle card element left neighbouir is smaller than middle element then left half must have a local min, hence we recurse in left half
c, if right neighbour is less than middle element we will recurse the right half
we can do this, because we know the end points and the local minima must exist in one of the halves, since its not monotonic.
This always divides array into halfes and works on them, hence the order is O(log n)
Thumbs up if this was helfpul, otherwise let me know in comments.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.