Problem

At Stripe, you need a fast way to locate a value in a sorted list of integers. Implement binary search to return the index of a target value, or -1 if the target is not present.

Formal Specification

Write a function that takes:

• nums: a list of integers sorted in non-decreasing order
• target: an integer to search for

Return:

• The index of target in nums if it exists
• -1 otherwise

If the target appears multiple times, returning any valid index is acceptable.

Examples

Example 1

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

Explanation: nums[4] is 9, so the function returns 4.

Example 2

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

Explanation: 2 does not appear in the array.

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i], target <= 10^9
• nums is sorted in non-decreasing order
• Your solution should run in O(log n) time