Binary Search

Binary Search

Given a sorted array of distinct integers nums and a target value, return the index of the target if it exists in the array. If the target is not found, return -1.

You must write an algorithm with O(log n) runtime complexity.

Examples

Example 1:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4.

Example 2:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1.

Example 3:

Input: nums = [5], target = 5
Output: 0

Constraints

• 1 <= nums.length <= 10^4
• -10^4 < nums[i], target < 10^4
• All integers in nums are unique.
• nums is sorted in ascending order.

Expected Complexity

• Time: O(log n)
• Space: O(1)