216. Binary Search by Recursion
You are given n integers in increasing order, then a value x. Print the
0-based position of x, or -1 if it is not there.
Look at the middle element. If it is x you are done. If it is smaller, x
can only be in the right half; if it is larger, only in the left. Each step
throws away half of what is left, so a million elements takes about twenty
steps rather than a million.
Two mistakes end this in an infinite loop, and both are worth meeting once:
writing lo = mid instead of lo = mid + 1, and computing the midpoint in a
way that overflows.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - The values are strictly increasing.
Input
The first line contains two integers n and x.
The second line contains n integers in increasing order.
Output
Print one integer: the 0-based position of x, or -1 if it is absent.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.