Codeforces Round #703 Guessing the Greatest - Binary search
Solution:
Let's query $[1,n]$ firstly. And we get the index of 2nd largest value. Now we can get picture below:
We divide the segment into two parts. And query the side which closes to 2nd largest value. So we can get the picture below:
If the largest value in the part we queried. Then it will return the index of 2nd largest value again. Otherwise, it will return the index of value smaller than 2nd largest value.
Now we divide the possible segment into two parts again. And query the side which closes to 2nd largest value again. (If the 2nd largest value is out of the segment, then extend the segment until including it.). Please check the picture below for an example:
So we reduced the scale of the problem by half. Repeatedly, we can compress the possible interval length to 1 within the number of $log(n)$.