Binary Search Foundations

7 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

What is Binary Search?

Binary Search is a search algorithm that finds the position of a target value within a SORTED collection. Instead of checking every element one by one (linear search), it repeatedly divides the search space in half. Each comparison eliminates half of the remaining elements, making it incredibly efficient: O(log n) vs O(n).

The intuition

Imagine guessing a number between 1 and 100. Your friend says 'higher' or 'lower' after each guess. Would you guess 1, 2, 3...? No! You'd guess 50 first, then 25 or 75, cutting the possibilities in half each time. That's binary search!

Requires SORTED data, this is a prerequisite
Eliminates HALF the search space each step
Uses two pointers: left and right to define the search window
O(log n) time: searching 1 billion items takes only ~30 steps!
Much faster than linear search O(n) for large datasets

When to use it

When data is sorted (or can be sorted)
When you need O(log n) search performance
When finding boundaries (first/last occurrence)
When searching on a monotonic function

A real-world analogy

Think of looking up a word in a physical dictionary. You don't start from page 1. You open roughly to the middle, check if your word comes before or after, then flip to the middle of the remaining half. Each flip halves your search space!

Basic Binary Search

The classic binary search: given a sorted array and a target, find its index. Start with left=0 and right=n-1. Compute mid = left + (right-left)/2. If nums[mid] == target, found it! If nums[mid] < target, search right half (left = mid+1). If nums[mid] > target, search left half (right = mid-1). Repeat until left > right.

The intuition

You're looking for a specific book on a numbered shelf. You check the middle book. Too low? Ignore the entire left half. Too high? Ignore the entire right half. Keep halving until you find it or run out of shelf.

Initialize: left = 0, right = n - 1
Loop while left <= right
mid = left + (right - left) // 2 (avoids overflow!)
If target found at mid → return mid
If target > nums[mid] → search right: left = mid + 1
If target < nums[mid] → search left: right = mid - 1
Return -1 if not found

Time complexity

Best	O(1)
Average	O(log n)
Worst	O(log n)

Space complexity: O(1) iterative, O(log n) recursive

When to use it

Finding exact match in a sorted array
Checking if an element exists
Foundation for all binary search variants

A real-world analogy

Playing the number guessing game with 'higher' / 'lower' hints. Each hint eliminates exactly half the remaining possibilities!

def binary_search(nums, target):
    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

Lower Bound (First Occurrence)

Sometimes the target appears multiple times and you need the FIRST occurrence (leftmost position). Or you need the first element >= target (lower bound). The trick: when you find the target, DON'T stop! Instead, save the position and keep searching LEFT (right = mid - 1) to see if there's an earlier occurrence.

The intuition

Imagine a row of students sorted by height. You want to find where 170cm students START. You find one at position 5, but there might be more 170cm students before position 5. So you keep looking left to find the very first one.

Don't return immediately when target is found
When nums[mid] >= target: save mid as answer, search LEFT (right = mid - 1)
When nums[mid] < target: search RIGHT (left = mid + 1)
Final answer is the saved position
Also called 'bisect_left' in Python

Time complexity

Best	O(1)
Average	O(log n)
Worst	O(log n)

Space complexity: O(1)

When to use it

Finding first occurrence of a value
Finding insertion point (leftmost)
Finding first element >= target
Search Insert Position problem

A real-world analogy

In a phone book with duplicate names, finding the FIRST 'Smith'. You can't stop at the first one you see, you need to check if there are earlier Smiths.

def lower_bound(nums, target):
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            result = mid  # save and search left
            right = mid - 1
        else:
            left = mid + 1
    return result

Upper Bound (Last Occurrence)

The mirror of lower bound: find the LAST occurrence of the target (rightmost position). When you find the target, save the position and keep searching RIGHT (left = mid + 1). Combined with lower bound, you can find the range [first, last] of any target value.

The intuition

Same row of students: now you want to find where 170cm students END. You find one at position 5, but there might be more after. So you keep looking right to find the very last one.

When nums[mid] <= target: save mid, search RIGHT (left = mid + 1)
When nums[mid] > target: search LEFT (right = mid - 1)
Pairs with lower bound to find complete range
Also called 'bisect_right - 1' in Python

Time complexity

Best	O(1)
Average	O(log n)
Worst	O(log n)

Space complexity: O(1)

When to use it

Finding last occurrence of a value
Finding the range of a target [first, last]
Counting occurrences = last - first + 1
Find First and Last Position problem

A real-world analogy

Finding the LAST page in a book chapter. You know you're in chapter 5, but you keep flipping forward until you hit chapter 6, then go back one page.

def upper_bound(nums, target):
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            result = mid  # save and search right
            left = mid + 1
        else:
            right = mid - 1
    return result

Search in Rotated Array

A sorted array that's been rotated (e.g., [4,5,6,7,0,1,2]) is no longer fully sorted, but ONE HALF is always sorted! At each step, determine which half is sorted, then check if the target lies in that sorted half. If yes, search there. If no, search the other half.

The intuition

Imagine a clock where the numbers 1-12 are in order, but someone rotated the dial. You can still find any number efficiently because at least half the visible range is always in order. Use that ordered half to decide which way to go!

After rotation, ONE half is always sorted
Check if left half is sorted: nums[left] <= nums[mid]
If sorted half contains target → search there
Otherwise → search the other half
Handle the pivot/minimum implicitly

Time complexity

Best	O(1)
Average	O(log n)
Worst	O(log n)

Space complexity: O(1)

When to use it

Searching in a rotated sorted array
Finding the minimum in a rotated array
When data was sorted but shifted/rotated

A real-world analogy

A conveyor belt of sorted packages that someone started midway. You can still binary search by checking which section of the belt is in order and deciding if your package is in that section.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # left sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                        # right sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Binary Search on Answer

The most powerful pattern! Instead of searching an array, you binary search on the ANSWER SPACE. If the answer must be between min_val and max_val, binary search that range. For each candidate answer (mid), check if it's feasible using a helper function. This transforms optimization problems into binary search!

The intuition

A factory needs to find the minimum production speed to finish orders on time. Instead of trying every speed, binary search between 1 and max_speed. For each speed, simulate: can we finish on time? If yes, try slower. If no, go faster.

Define the answer space: [low, high]
Write a feasibility check function: canAchieve(mid)
If canAchieve(mid) is true → try smaller (right = mid - 1)
If canAchieve(mid) is false → try larger (left = mid + 1)
Works when: if answer X works, then X+1 also works (monotonic)

Time complexity

Best	O(log(range) × check)
Average	O(log(range) × check)
Worst	O(log(range) × check)

Space complexity: O(1) extra

When to use it

Minimize the maximum / Maximize the minimum problems
Koko Eating Bananas, Ship Packages, Split Array
Any optimization with a monotonic feasibility function
When answer range is known and check is efficient

A real-world analogy

Setting a speed limit on a highway. Too slow = traffic jams (not feasible). Too fast = unsafe. Binary search the sweet spot: try 60 mph → check → adjust up or down.

def binary_search_on_answer(low, high):
    result = high
    while low <= high:
        mid = low + (high - low) // 2
        if canAchieve(mid):
            result = mid   # save and try smaller
            high = mid - 1
        else:
            low = mid + 1
    return result

Patterns & Pitfalls

Binary search has several common patterns and pitfalls. The three main templates are: (1) Exact match. Return when found, (2) Left boundary. Keep going left after finding, (3) Right boundary, keep going right after finding. Common bugs include off-by-one errors, infinite loops from wrong mid calculation, and forgetting the sorted prerequisite.

The intuition

Think of binary search as a decision tree. At every node you ask: go left or right? The three patterns differ only in what you do when you FIND the target. Exact match: stop. Left boundary: go left. Right boundary: go right.

Always use mid = left + (right - left) // 2 to avoid overflow
Watch for infinite loops: ensure left or right changes every iteration
Template 1 (exact): while left <= right, return mid when found
Template 2 (left bound): while left <= right, right = mid - 1 when found
Template 3 (right bound): while left <= right, left = mid + 1 when found
Off-by-one: does your answer need mid, mid-1, or mid+1?

When to use it

Use exact match for simple lookups
Use left boundary for first occurrence / insertion point
Use right boundary for last occurrence
Use answer space for optimization problems

A real-world analogy

Like learning to drive: once you master the three basic maneuvers (park, turn, reverse), you can handle any road. Master these three binary search templates and you can solve almost any binary search problem!

All DSA learning paths