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 order