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).

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

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.

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

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.

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

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.

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

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.

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

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!

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)

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.

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?

All DSA learning paths