704. Binary Search — LeetCode(Python)

I got you!

Problem:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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:

The algorithm is pretty standard. We create two pointers on left and right ends of our array nums.

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:

We are dividing the array into equal halves on every iteration, until only a single number is left in the array, after which our termination l ≤ r becomes False.

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:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏