216. Binary Search
Core1000 ms256 MBSolved by 0%
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.
Input5 7
1 3 5 7 9
Output3
Notefinds a value in the middle-right of the array
Input5 4
1 3 5 7 9
Output-1
Notelooks for a value that is not present at all
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution