I got you!

# Problem:

You must write an algorithm with `O(log n)` runtime complexity.

Example 1:

`Input: nums = [-1,0,3,5,9,12], target = 9Output: 4Explanation: 9 exists in nums and its index is 4`

Example 2:

`Input: nums = [-1,0,3,5,9,12], target = 2Output: -1Explanation: 2 does not exist in nums so return -1`

Constraints:

• `1 <= nums.length <= 104`
• `-104 < nums[i], target < 104`
• All the integers in `nums` are unique.
• `nums` is sorted in ascending order.

# Solution:

`l, r = 0, len(nums) - 1        while l <= r:    mid = (l + r) // 2    if nums[mid] == target:        return mid    elif nums[mid] < target:        l = mid + 1    else:        r = mid - 1                return -1`

## Explanation:

Then we calculate our array’s mid element.

If this index contains the target value, we return this index.

Since, we know that the array is sorted, we check if the target value is greater than the element we’re at. If yes, we check only the right subarray, which has larger values than nums[mid]. We accomplish this by shifting our left pointer to the index after mid.

And if the target value is less than our current element, we only check the left subarray, which has smaller values than nums[mid]. We accomplish this by shifting our right pointer to the index before mid.

If we don’t come across the target value in the array, we return -1.

## Time and Space Complexity:

And, we know, the number of times we can divide a number by two to reach one, is log2(n). [2 is the base]

We also note that we require a constant amount of extra space for our algorithm.

Thus, if n is the length of the array nums,

Time Complexity: O(log(n))

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

# I don’t have friends:

Connect with me on:

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

## More from Palash Sharma

A student of science | palashsharma891@gmail.com | https://github.com/palashsharma891 | https://www.linkedin.com/in/palashsharma891/