Binary Search

PracticeNeetCode ↗LeetCode ↗

Given a sorted array of unique integers nums and an integer target, return the index of target if it exists in the array, otherwise return -1. The solution must run in O(log n) time.

Example

Key Pointers

• The array being sorted is exactly what allows discarding half the search space on every step.
• Track two pointers, left and right, and compute mid as left + (right - left) // 2 to avoid overflow habits carried over from other languages.
• Narrow the range by comparing the middle value to the target, and stop as soon as the pointers cross.

Step-by-Step Analysis

1. Set left = 0, right = len(nums) - 1.
2. While left is not past right: compute mid partway between them.
3. If nums[mid] equals the target, return mid.
4. If nums[mid] is smaller than the target, search the right half; otherwise search the left half.
5. If the loop ends without a match, return -1.

Complexity

Time: O(log n) — Space: O(1)

Code

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Code Explanation

How the solution above works, piece by piece.

1. left and right bound the part of the array where the target can still be.
2. mid = left + (right - left) // 2 is the middle. Written this way it can't overflow in fixed-size integer languages.
3. Equal → found. Smaller → the target is to the right, so left = mid + 1. Larger → right = mid - 1. mid itself is excluded both times since it was just checked.
4. while left <= right keeps going while at least one candidate remains; if the range empties, return −1.
5. Each step halves the range: O(log n) time, O(1) space.

Visual Walkthrough

Running it on nums = [-1, 0, 3, 5, 9, 12], target = 9:

Video Explanation

NeetCode — Binary Search, LeetCode 704