At Stripe, a service stores sorted numeric IDs in memory and needs fast lookups. Implement binary search to find the index of a target value in a sorted array.
Given a sorted list of integers nums in ascending order and an integer target, return the index of target if it exists. Otherwise, return -1.
nums (list of integers sorted in ascending order), target (integer)target, or -1 if not foundExample 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 ascending ordernums are distinctYour solution should run in O(log n) time.