Why I didn’t solve it

I realizee that I can use bsearch and detect the direction of points by asking (i, i+1). However, I got stuck at handling the answer to my query => i.e., what does the answer mean?

Insights

  1. (mid, mid+1) returns true => there must exist one point to the left of mid, including mid

  2. returns false => there must exist one point to the right of mid+1, include mid + 1

  3. So we can just do a bsearch, and we know there must exist an point in our range, and we can definitely find one => when r - l = 1

  4. Now that we repeat similar bsearch in [1, mid) and (mid + 1, n], we know that at least one points in the intervals for sure

  5. Note that to root out false positvies, we need to specifically check the second point’s validity by issuing another query!!!

  6. Need to handle the case of first return is 1 or n with special care!!!