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.
Write a function that takes:
nums: a list of integers sorted in non-decreasing ordertarget: an integer to search forReturn:
target in nums if it exists-1 otherwiseIf the target appears multiple times, returning any valid index is acceptable.
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.
0 <= len(nums) <= 10^5-10^9 <= nums[i], target <= 10^9nums is sorted in non-decreasing orderO(log n) time