Binary Search

nums is sorted in ascending order with distinct values. Return the index of target, or -1 if it isn’t present. Your algorithm must run in O(log n).

Examples

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Constraints

• 1 ≤ nums.length ≤ 10⁴, distinct, sorted ascending.

Explanation

Intuition

Compare target with the middle element. Because the array is sorted, one comparison rules out half the remaining elements.

Algorithm

Keep the search range [lo, hi] (inclusive). While lo ≤ hi:

• mid = lo + (hi − lo) / 2 (written this way to avoid integer overflow of lo + hi in other problems).
• If nums[mid] == target, return mid.
• If nums[mid] < target, the answer can only be to the right: lo = mid + 1.
• Otherwise hi = mid − 1.

If the range becomes empty, the target isn’t there.

Complexity

• Time: O(log n) — 10⁴ elements need at most 14 comparisons. Space: O(1).