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) timenums = [-1, 0, 3, 5, 9, 12], target = 9Output4WhyThe target `9` is present at index `4`.nums = [-1, 0, 3, 5, 9, 12], target = 2Output-1WhyThe target `2` is not in the sorted array.nums = [1], target = 1Output0WhyThe array has one element, and it matches the target.0 <= len(nums) <= 10^5-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9nums is sorted in non-decreasing orderReturn any valid index if duplicates existdef binary_search(nums, target):