Flipper Card Analysis

Question

I will pass an exam in the Data Structures class soon. To prepare, I look at some problems based on an algorithm that I found on the Internet, and run one that, as I can, seems to fail.

You go into the room and see a row of n cards. Each of them has a number xi written on it, where I range from 1 to n. However, initially all cards are face down. Your goal is to find a local minimum: that is, a card whose number is less than or equal to the number of its neighbors, xi-1> = xi <= xi + 1. The first and last cards can also be local minima, and they only have one neighbor compared to. It is clear that there can be many local minima, but you are only responsible for finding one of them.

The only solution I can come up with basically minimizes them and finds any local lows. However, the challenge is to do this only by flipping the O (logn) cards.

Essentially, if you see the card "7", this is a local minimum if the card on the left is "10" and the card on the right is "9". How easy is it to do during login?

Any thanks, thanks.

Answer 1

Binary search is the way to go. Here is a rough sketch of how you can do this:

• Look at the first and last elements. If either there is a minus, return it.
• Look at the middle element. If it is a minimum refund. Otherwise, his left neighbor or right neighbor must be smaller than him. Count this half.

So, the idea is that if we know that the left neighbor of the central element is smaller than his, then the left half should have a local minimum somewhere so that we can safely return there. The same goes for the right half.

In other words, the only way that half of the data will not have a local mine is that it is either monotonous or moves up and back, both of which cannot happen, because we know the values ​​of the endpoint.

In addition, the execution time is clearly logarithmically (n), because each step takes constant time, and we must execute the log (n) steps, because every time we cut the data in half.