Binary Search

Problem

You are given an array of integers nums sorted in non-decreasing order and an integer target. Return the index at which target appears in nums. If it does not appear, return -1. A linear scan is not an acceptable answer; the solution should do logarithmically many comparisons.

• nums may be empty and holds at most 50,000 elements.
• Values and target are integers in the range -100,000 to 100,000.
• If target occurs more than once, any matching index is acceptable.

Examples

• nums = [2, 4, 7, 10, 15, 21, 30], target = 15 → 4, because nums[4] == 15.
• nums = [2, 4, 7, 10, 15, 21, 30], target = 8 → -1; 8 falls between 7 and 10 but is not present.
• nums = [3], target = 3 → 0. A one-element array still needs the loop to terminate correctly.

Hints

1. The array is sorted. Comparing target to one element tells you which side it could be on.
2. Keep two indices that bracket the region where the answer could still live, and shrink that region every step.
3. Classic binary search with an inclusive [lo, hi] window; stop when the window is empty.