Binary Search

Count Vowels

Valid Anagram

Locate a target in a sorted unique array using logarithmic search.

Given an ascending array of distinct integers, return the index of `target` or `-1` when it is absent.

**Input / output**
- Input: `nums: integer[]`, `target: integer`
- Output: zero-based integer index

**Examples**
1. `nums = [-1,0,3,5,9,12], target = 9` returns `4`.
2. The same array with `target = 2` returns `-1`.

**Constraints**
- `0 <= nums.length <= 100,000`
- Values are strictly increasing

**Follow-up**
Explain the loop invariant and how you avoid midpoint overflow in fixed-width integer languages.

- 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).