Return the index of target in a sorted array, or -1 if not present.

Interview question: Binary Search

Given a sorted (ascending) array of integers `nums` and an integer `target`, return the index of `target` if it exists in `nums`, otherwise return `-1`.

Your solution should run in `O(log n)` time.

- The array is sorted in ascending order.
- You need return the index of `target`, or `-1` if it is missing.
- The requested O(log n) time means we should repeatedly discard half of the search range.

Understand the Sorted Input

- Checking each element from left to right is simple and correct.
- However, it can inspect every value in the worst case.
- That makes it O(n), which does not meet the requirement.

Why Linear Search Is Not Enough

- Binary search keeps two pointers: `left` and `right`.
- Look at the middle index between them.
- If the middle value is too small, search the right half; if it is too large, search the left half.

Use the Middle Element

- When `nums[mid] < target`, all values at `mid` and left of it are too small, so move `left` to `mid + 1`.
- When `nums[mid] > target`, all values at `mid` and right of it are too large, so move `right` to `mid - 1`.
- Stop when the bounds cross.

Update the Search Bounds

- The equality check returns immediately when the target is found.
- Each loop removes about half of the remaining values.
- Time complexity is O(log n), and space complexity is O(1).