704. Binary Search — LeetCode(Python)

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 = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 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:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store