Sorted array. Halve search space each step. Mid = L + (R-L)/2.
Input
6 9 -1 0 3 5 9 12
Output
4
6 2 -1 0 3 5 9 12
-1