LeetCode 704: Binary Search

Problem Restatement

We are given an array of integers nums.

The array is sorted in ascending order.

We are also given an integer target.

We need to find target in nums.

If target exists, return its index.

If target does not exist, return:

-1

The required runtime is O(log n), so we should use binary search instead of scanning the array one element at a time.

Input and Output

The function shape is:

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        ...

Examples

Example 1:

nums = [-1, 0, 3, 5, 9, 12]
target = 9

The value 9 appears at index 4.

So the answer is:

4

Example 2:

nums = [-1, 0, 3, 5, 9, 12]
target = 2

The value 2 does not appear in the array.

So the answer is:

-1

First Thought: Linear Search

The simplest solution is to check every element from left to right.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i

        return -1

This is correct, but it does not satisfy the required runtime.

If the array has n elements, linear search can take:

O(n)

The problem asks for O(log n), so we need to use the sorted order.

Key Insight

Because the array is sorted, we can discard half of the remaining search space after each comparison.

Pick the middle index.

If the middle value equals target, we are done.

If the middle value is smaller than target, then every value on the left side is also too small. We only need to search the right half.

If the middle value is larger than target, then every value on the right side is also too large. We only need to search the left half.

This is binary search.

Algorithm

Use two pointers:

left = 0
right = len(nums) - 1

These pointers describe the current search range.

While left <= right:

1. Compute the middle index.
2. Compare nums[mid] with target.
3. If they are equal, return mid.
4. If nums[mid] < target, move left to mid + 1.
5. If nums[mid] > target, move right to mid - 1.

If the loop ends, the target is not in the array.

Return -1.

Correctness

At the start, the search range is the entire array.

During each iteration, the algorithm chooses the middle index mid.

If nums[mid] == target, returning mid is correct.

If nums[mid] < target, then every index from left through mid contains a value less than or equal to nums[mid], because the array is sorted. Therefore none of those values can be target. Removing them from the search range is safe.

If nums[mid] > target, then every index from mid through right contains a value greater than or equal to nums[mid]. Therefore none of those values can be target. Removing them from the search range is safe.

So after every step, if target exists, it remains inside the current search range.

When the range becomes empty, there is no possible index left where target can appear. Returning -1 is correct.

Complexity

Implementation

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

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

Code Explanation

We begin with the full array as the search range:

left = 0
right = len(nums) - 1

The loop continues while the range is valid:

while left <= right:

The middle index is:

mid = left + (right - left) // 2

This form avoids overflow in languages with fixed-size integers. In Python, overflow is not a practical issue, but this version is still a good habit.

If the middle value is the target, return the index:

if nums[mid] == target:
    return mid

If the middle value is too small, the target can only be on the right:

if nums[mid] < target:
    left = mid + 1

Otherwise, the middle value is too large, so the target can only be on the left:

else:
    right = mid - 1

If the loop finishes, the target was not found:

return -1

Testing

def test_search():
    s = Solution()

    assert s.search([-1, 0, 3, 5, 9, 12], 9) == 4
    assert s.search([-1, 0, 3, 5, 9, 12], 2) == -1
    assert s.search([5], 5) == 0
    assert s.search([5], -5) == -1
    assert s.search([1, 2, 3, 4, 5], 1) == 0
    assert s.search([1, 2, 3, 4, 5], 5) == 4
    assert s.search([-10, -3, 0, 7, 11], -3) == 1

    print("all tests passed")

test_search()

Test coverage: