Leetcode 704. Binary Search

Problem

Leetcode 704. Binary Search

Example:

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

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

Approach

This is a simple binary search problem. I will get more in depth on binary search in a future post, but for now we can use two pointers to find the target. We run a while loop until the two pointers meet in the middle. There are 3 scenarios:

1. The middle element is the target. We return the index.
2. The target is less than the middle element. We move the right pointer to the middle - 1.
3. The target is greater than the middle element. We move the left pointer to the middle + 1.

We continue this process until we find the target or the pointers meet.

If the target is not found, we return -1.

Visual representation of the binary search:

target = 9
[-1,0,3,5,9,12]
  L          R
nums[mid] = 3       Since 3 < 9, we move the left pointer to mid + 1

[-1,0,3,5,9,12]
        L   R
nums[mid] = 9       Since 9 == 9, we return the index

index = 4

Here is the implementation of the binary search:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        # We run a while loop until the two pointers meet
        while left <= right:
            # We calculate the middle index
            mid = (left + right) // 2

            # Case 1: If the middle element is the target, we return the index
            if nums[mid] == target:
                return mid
            # Case 2: If the target is greater than the middle element, we move the left pointer to mid + 1
            elif nums[mid] < target:
                left = mid + 1
            # Case 3: If the target is less than the middle element, we move the right pointer to mid - 1
            else:
                right = mid - 1
        return -1

Time Complexity and Space Complexity

The time complexity of the binary search is $ O(\log{n}) $ because we are halving the search space with each iteration.

The space complexity is $ O(1) $ because we are not using any extra space.