Binary Search

Given a sorted integer array nums and an integer target, return the index of target in the array. If it does not exist, return -1.

You must write an algorithm that runs in O(log n) time.

---

Example 1

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 is at index 4 in the sorted array.

Example 2

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

---

Constraints

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