Binary Search: Templates for Classic, Bound and Answer Search

Coding Patterns - Guide to 30 Core Algorithm Patterns

Binary Search: Complete Guide with Advanced Variations

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here runs in

O(log N)

time with

O(1)

extra space unless otherwise noted.

Main Template: Standard Binary Search

Use this template when you need to find the exact index of an element in a sorted array with no duplicates, or when any index of the target is acceptable.

Use this for Binary Search .

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        // mid is the midpoint of the current window.
        // Use floor division to land on an index in the lower half.
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; // target is in the right half
        } else {
            right = mid - 1; // target is in the left half
        }
    }

    return -1;
}

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

left: the left boundary of the current search window. Initially 0. Points to the smallest index that could still contain the target.
right: the right boundary. Initially nums.length - 1. Points to the largest index that could still contain the target.
mid: the midpoint of the current window, calculated as left + (right - left) / 2. This avoids overflow by never adding left and right directly.

Visual Mechanism

    graph TD
    Start[Start] --> Loop{"left <= right?"}
    Loop -->|Yes| Mid[Calculate Mid]
    Mid --> Equal{"nums[mid] == target?"}
    Equal -->|Yes| Found[Return mid]
    Equal -->|No| Compare{"nums[mid] < target?"}
    Compare -->|Yes| Right[left = mid + 1]
    Compare -->|No| Left[right = mid - 1]
    Right --> Loop
    Left --> Loop
    Loop -->|No| NotFound[Return -1]

Critical Sections

The initialization sets left and right to cover the entire array. Using 0 and n - 1 means the window includes every element, which is correct for a standard search.

The loop condition left <= right ensures that when left and right converge on the same index, that last element still gets checked. If the loop used < instead, the final element would be skipped.

The shrink step always moves left or right past mid. Setting left = mid + 1 when the target is larger than nums[mid] eliminates both mid and everything left of it. Setting right = mid - 1 when the target is smaller eliminates mid and everything right of it. This guarantees the window shrinks on every iteration and cannot loop infinitely.

Variations

1. Finding Boundaries (First and Last Occurrence)

When the array contains duplicates and you need the first or last position of the target, you modify the standard template to keep searching after a match.

Use this for First and Last Position of Element in Sorted Array .

function findBound(nums, target, isFirst) {
    let left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
            result = mid;
            if (isFirst) right = mid - 1;  // keep searching left
            else left = mid + 1;            // keep searching right
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

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

public int findBound(int[] nums, int target, boolean isFirst) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            if (isFirst) right = mid - 1;
            else left = mid + 1;
        } else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

int findBound(vector<int>& nums, int target, bool isFirst) {
    int left = 0, right = nums.size() - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            if (isFirst) right = mid - 1;
            else left = mid + 1;
        } else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

func findBound(nums []int, target int, isFirst bool) int {
    left, right := 0, len(nums)-1
    result := -1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            result = mid
            if isFirst {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return result
}

The key difference from the standard template is that result is recorded on every match, and the search continues in the direction of interest. For the first occurrence, move right left past mid to keep scanning the left half for an earlier match. For the last occurrence, move left right past mid to scan the right half.

2. Binary Search on Answer

Some problems do not give you a sorted array to search. Instead, you search the space of possible answers. This works when the answer has a monotonic property: if a candidate value K works, then any value larger than K also works (or vice versa).

Use this for Koko Eating Bananas .

Time complexity is

O(N log M)

where M is the range of possible answers and N is the cost to check one candidate.

function minEatingSpeed(piles, h) {
    let left = 1, right = Math.max(...piles);
    let result = right;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        // Can Koko finish at speed mid?
        if (canEatAll(piles, h, mid)) {
            result = mid;      // mid works, try slower
            right = mid - 1;
        } else {
            left = mid + 1;    // mid is too slow
        }
    }
    return result;
}

function canEatAll(piles, h, speed) {
    let hours = 0;
    for (const pile of piles) {
        hours += Math.ceil(pile / speed);
    }
    return hours <= h;
}

def min_eating_speed(piles: list[int], h: int) -> int:
    left, right = 1, max(piles)
    result = right

    while left <= right:
        mid = left + (right - left) // 2
        if can_eat_all(piles, h, mid):
            result = mid
            right = mid - 1
        else:
            left = mid + 1

    return result

def can_eat_all(piles: list[int], h: int, speed: int) -> bool:
    total_hours = 0
    for pile in piles:
        total_hours += (pile + speed - 1) // speed
    return total_hours <= h

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = 0;
    for (int p : piles) right = Math.max(right, p);
    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canEatAll(piles, h, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

private boolean canEatAll(int[] piles, int h, int speed) {
    int hours = 0;
    for (int p : piles) {
        hours += (p + speed - 1) / speed;
    }
    return hours <= h;
}

int minEatingSpeed(vector<int>& piles, int h) {
    int left = 1, right = *max_element(piles.begin(), piles.end());
    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canEatAll(piles, h, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

bool canEatAll(vector<int>& piles, int h, int speed) {
    long hours = 0;
    for (int p : piles) {
        hours += (p + speed - 1) / speed;
    }
    return hours <= h;
}

func minEatingSpeed(piles []int, h int) int {
    left, right := 1, 0
    for _, p := range piles {
        if p > right {
            right = p
        }
    }
    result := right

    for left <= right {
        mid := left + (right-left)/2
        if canEatAll(piles, h, mid) {
            result = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return result
}

func canEatAll(piles []int, h int, speed int) bool {
    hours := 0
    for _, p := range piles {
        hours += (p + speed - 1) / speed
    }
    return hours <= h
}

def min_eating_speed(piles, h)
    left, right = 1, piles.max
    result = right

    while left <= right
        mid = left + (right - left) / 2
        if can_eat_all(piles, h, mid)
            result = mid
            right = mid - 1
        else
            left = mid + 1
        end
    end

    result
end

def can_eat_all(piles, h, speed)
    hours = 0
    piles.each do |p|
        hours += (p.to_f / speed).ceil
    end
    hours <= h
end

The key difference from standard binary search is that the comparison is not nums[mid] == target but a predicate function that checks feasibility. The search range is the space of possible answers, not the array indices. The result tracks the last feasible value as the search narrows to find the minimum feasible answer.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .