Problem

Implement a binary search algorithm that finds the index of a target value in a sorted array. If the target value is not found, return -1.

Input

• A sorted list of integers nums.
• An integer target to search for.

Output

• The index of target in nums or -1 if target is not present.

Examples

Example 1:

Input: nums = [1, 2, 3, 4, 5], target = 3
Output: 2

Example 2:

Input: nums = [1, 2, 3, 4, 5], target = 6
Output: -1

Constraints

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• nums is sorted in ascending order.