A product team at Stripe stores item IDs in a sorted list and needs fast lookup. Implement an efficient search algorithm that returns the index of a target value in a sorted integer array.
Write a function that takes:
nums: a list of integers sorted in ascending ordertarget: an integer to search forReturn:
target if it exists in nums-1 if target is not presentYou must solve this in O(log n) time.
Example 1
nums = [-1, 0, 3, 5, 9, 12], target = 94nums[4] is 9, so return 4.Example 2
nums = [-1, 0, 3, 5, 9, 12], target = 2-12 does not appear in the array.1 <= len(nums) <= 10^5-10^9 <= nums[i], target <= 10^9nums is sorted in strictly increasing ordernums = [-1, 0, 3, 5, 9, 12], target = 9Output4WhyThe target `9` appears at index `4`.nums = [-1, 0, 3, 5, 9, 12], target = 2Output-1WhyThe value `2` is not in the sorted array.nums = [5], target = 5Output0WhyThe array has one element, and it matches the target.1 <= len(nums) <= 10^5-10^9 <= nums[i], target <= 10^9nums is sorted in strictly increasing orderAn O(log n) solution is requireddef binary_search(nums, target):