#28 Easy Time O(log n) Space O(1) Animated

Binary Search

Search a sorted array for a target value using binary search.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Binary search over a monotonic decision

Each comparison proves that half of the remaining search space cannot contain the answer.

Approach: Binary Search — Classic

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Each comparison proves that half of the remaining search space cannot contain the answer.

Common Pitfall

Choose inclusive or exclusive bounds once and update them consistently.

Description

Search a sorted array for a target value using binary search.

Constraints

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

Solution — Binary Search — Classic

TimeO(log n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Set the initial bounds.
Compute a midpoint.
Use the monotonic condition to discard one half.
Return when found or when the bounds cross.

def search(nums, target):
    left, right = 0, len(nums) - 1  # line 1
    while left <= right:             # line 2
        mid = (left + right) // 2    # line 3
        if nums[mid] == target:      # line 4
            return mid               # line 5
        elif nums[mid] < target:     # line 6
            left = mid + 1           # line 7
        else:                        # line 8
            right = mid - 1          # line 9
    return -1                        # line 10

Search a 2D Matrix

Binary Search

Steps

Description

Constraints

Tags

Solution — Binary Search — Classic