Card Flipper: You walk into a room, and see a row of n cards. Each one has a num
ID: 3832211 • Letter: C
Question
Card Flipper: You walk into a room, and see a row of n cards. Each one has a number xi written on it, where i ranges from 1 to n. However, initially all the cards are face down. Your goal is to find a local minimum: that is, a card i whose number is less than or equal to those of its neighbors, xi-1 >= xi <= xi+1. The first and last cards can also be local minima, and they only have one neighbor to compare to. There can be many local minima, but you are only responsible for finding one of them. Obviously you can solve this problem by turning over all n cards, and scanning through them. However, show that you can find such a minimum by turning over only O(log n) cards.
Explanation / Answer
Binary search is solution for your question. Here, is an idea of how you can implement it in your case :
So the idea is if you know that left neighbor of the center element is < than it, then the left half must be having a local min somewhere, so we can safely Recurse there again and again. The same goes for the right half part.
Said differently, the only way that half of the data will not be having a local min is that if it is either 'monotonic' or Goes up and Back down, both of which can not happen, because we know the end points values.
Also, the runtime is clearly 'log(n)' .
Because, each step take constant time & we have to do log(n) steps only because we cut the data in half each time.