Oct 1, 2025

Binary Search

Overview

Binary search repeatedly discards half of a search space. The familiar version searches a sorted array, but the same idea works whenever the possible answers have a monotonic property: once a condition becomes true, it stays true for every larger answer, or vice versa.

A binary search solution usually runs in O(log n) time and uses O(1) extra space. The difficult part is not calculating the midpoint; it is defining an invariant that makes every boundary update correct. Before writing the loop, decide:

What does the search interval represent?
Is the interval closed ([left, right]) or half-open ([left, right))?
When the midpoint satisfies the condition, can it still be the answer?
Does the problem require any matching index, the first match, the last match, or the smallest feasible value?

Use left + (right - left) / 2 instead of (left + right) / 2 in Java to avoid integer overflow. After every iteration, the remaining interval must be strictly smaller.

Templates

The following three forms cover most binary search problems:

Exact match
- Start with the closed interval left = 0, right = n - 1.
- While left <= right, calculate mid.
- If values[mid] == target, return mid.
- If values[mid] < target, discard [left, mid] with left = mid + 1.
- Otherwise, discard [mid, right] with right = mid - 1.
- If the interval becomes empty, return -1.
Lower bound: first index whose value is at least the target
- Search the half-open interval [left, right), initially [0, n).
- While left < right, calculate mid.
- If values[mid] < target, set left = mid + 1.
- Otherwise, keep mid as a possible answer with right = mid.
- Return left; it may equal n when no qualifying element exists.
Binary search on an answer
- Identify an inclusive numeric range [low, high] containing every possible answer.
- Define feasible(candidate) so its result changes monotonically across that range.
- While low < high, calculate mid.
- If feasible(mid) is true, keep mid with high = mid.
- Otherwise, discard it with low = mid + 1.
- Return low, the smallest feasible answer.

import java.util.function.IntPredicate;

public class BinarySearchTemplates {
	public static int binarySearch(int[] values, int target) {
		int left = 0;
		int right = values.length - 1;

		while (left <= right) {
			int mid = left + (right - left) / 2;

			if (values[mid] == target) {
				return mid;
			}
			if (values[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}

		return -1;
	}

	public static int lowerBound(int[] values, int target) {
		int left = 0;
		int right = values.length;

		while (left < right) {
			int mid = left + (right - left) / 2;

			if (values[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return left;
	}

	public static int firstFeasible(int low, int high, IntPredicate feasible) {
		while (low < high) {
			int mid = low + (high - low) / 2;

			if (feasible.test(mid)) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}

		return low;
	}
}

from collections.abc import Callable

def binary_search(values: list[int], target: int) -> int:
	left = 0
	right = len(values) - 1

	while left <= right:
		mid = left + (right - left) // 2

		if values[mid] == target:
			return mid
		if values[mid] < target:
			left = mid + 1
		else:
			right = mid - 1

	return -1

def lower_bound(values: list[int], target: int) -> int:
	left = 0
	right = len(values)

	while left < right:
		mid = left + (right - left) // 2

		if values[mid] < target:
			left = mid + 1
		else:
			right = mid

	return left

def first_feasible(
	low: int,
	high: int,
	feasible: Callable[[int], bool],
) -> int:
	while low < high:
		mid = low + (high - low) // 2

		if feasible(mid):
			high = mid
		else:
			low = mid + 1

	return low

Problems

34. Find First and Last Position of Element in Sorted Array

Given a non-decreasing array, return the first and last indices containing the target, or [-1, -1] when it is absent. Use the same bisect_left implementation twice: search for target to find its first position, then search for target + 1 and subtract one to find its last position. The runtime is O(log n).

class Solution {
	public int[] searchRange(int[] nums, int target) {
		int N = nums.length;
		if (N == 0) {
			return new int[] {-1, -1};
		}

		int idx1 = binarySearch(nums, target);
		if (idx1 == N || nums[idx1] != target) {
			return new int[] {-1, -1};
		}

		int idx2 = binarySearch(nums, 1 + target);
		return new int[] {idx1, idx2 - 1};
	}

	// implementation of bisect_left
	private int binarySearch(int[] nums, int target) {
		int left = 0;
		int right = nums.length; // NOT nums.length - 1 !!!

		while (left < right) {
			int mid = (left + right) / 2;

			if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return left;
	}
}

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        if N == 0:
            return [-1, -1]

        idx1 = self.binarySearch(nums, target)
        if idx1 == N or nums[idx1] != target:
            return [-1, -1]

        idx2 = self.binarySearch(nums, 1 + target)
        return [idx1, idx2-1]

    # implementation of bisect_left
    def binarySearch(self, nums, target):
        left, right = 0, len(nums) # NOT len(nums) - 1 !!!
        while left < right:
            mid = (left + right)//2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

33. Search in Rotated Sorted Array

A sorted array of distinct values has been rotated at an unknown pivot. First binary search for the smallest value, which identifies the rotation point and divides the array into two sorted segments. Then run lower-bound search on the left segment and, if needed, the right segment. The three binary searches still take O(log n) time with O(1) extra space.

class Solution {
	public int search(int[] nums, int target) {
		int N = nums.length;
		int left = 0;
		int right = N - 1;

		while (left < right) {
			int mid = (left + right) / 2;
			if (nums[mid] > nums[N - 1]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		// when there is no rotation, left is 0 and the
		// left-segment search is automatically skipped
		int lMin = 0;
		int lMax = left - 1;
		int rMin = left;
		int rMax = N - 1;

		while (lMin < lMax) {
			int lMid = (lMin + lMax) / 2;
			if (nums[lMid] < target) {
				lMin = lMid + 1;
			} else {
				lMax = lMid;
			}
		}

		if (nums[lMin] == target) {
			return lMin;
		}

		while (rMin < rMax) {
			int rMid = (rMin + rMax) / 2;
			if (nums[rMid] < target) {
				rMin = rMid + 1;
			} else {
				rMax = rMid;
			}
		}

		return nums[rMin] == target ? rMin : -1;
	}
}

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        N = len(nums)
        left, right = 0, N - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid

        # pay attention to no ratation corner case where left = 0
        # should automatically skip left search
        l_min, l_max = 0, left-1
        r_min, r_max = left, N-1

        while l_min < l_max:
            l_mid = (l_min + l_max) // 2
            if nums[l_mid] < target:
                l_min = l_mid + 1
            else:
                l_max = l_mid

        if nums[l_min] == target:
            return l_min

        while r_min < r_max:
            r_mid = (r_min + r_max) // 2
            if nums[r_mid] < target:
                r_min = r_mid + 1
            else:
                r_max = r_mid

        return r_min if nums[r_min] == target else -1

300. Longest Increasing Subsequence

Maintain res[i - 1] as the smallest possible ending value of an increasing subsequence of length i. For each number, use lower-bound search to find the first ending value greater than or equal to it. Replace that ending value, or append the number when it extends the longest subsequence. This takes O(n log n) time and O(n) space.

import java.util.ArrayList;
import java.util.List;

class Solution {
	public int lengthOfLIS(int[] nums) {
		// res[i - 1]: smallest possible ending value of an
		// increasing subsequence of length i
		List<Integer> res = new ArrayList<>();
		res.add(nums[0]);

		for (int i = 1; i < nums.length; i++) {
			int idx = lowerBound(res, nums[i]);
			if (idx == res.size()) {
				res.add(nums[i]);
			} else {
				res.set(idx, nums[i]);
			}
		}

		return res.size();
	}

	private int lowerBound(List<Integer> res, int target) {
		int left = 0;
		int right = res.size();

		while (left < right) {
			int mid = left + (right - left) / 2;
			if (res.get(mid) < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return left;
	}
}

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # res[i - 1]: smallest possible ending value of an increasing subsequence of length i
        res = [nums[0]]

        for i in range(1, len(nums)):
            idx = bisect_left(res, nums[i])
            if idx == len(res):
                res.append(nums[i])
            else:
                res[idx] = nums[i]

        return len(res)

875. Koko Eating Bananas

Choose the smallest integer eating speed that lets Koko finish every pile within h hours. A speed is either too slow or feasible, and every speed above a feasible one is also feasible. Binary search the answer range from 1 to the largest pile and use the required number of hours as the monotonic feasibility check. The runtime is O(n log m), where m is the largest pile.

class Solution {
	public int minEatingSpeed(int[] piles, int h) {
		int left = 1;
		int right = 0;

		for (int p : piles) {
			right = Math.max(right, p);
		}

		while (left < right) {
			int mid = (left + right) / 2;

			if (canFinish(piles, h, mid)) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return left;
	}

	private boolean canFinish(int[] piles, int h, int k) {
		long total = 0;

		for (int p : piles) {
			total += (p + (long) k - 1) / k;
		}

		return total <= h;
	}
}

import math
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # can Koko finish eating all piles at this speeed k?
        def canFinish(k):
            total = 0
            for p in piles:
                total += math.ceil(p/k)

            return total <= h

        left, right = 1, max(piles)

        while left < right:
            mid = (left + right) // 2
            if canFinish(mid):
                right = mid
            else:
                left = mid + 1

        return left

1283. Find the Smallest Divisor Given a Threshold

Binary search the divisor from 1 through max(nums). As the divisor increases, the sum of the rounded-up quotients never increases, so isBelowThreshold is a monotonic predicate. Keep the feasible half and return the first divisor that satisfies the threshold. If M = max(nums), the runtime is O(n log M) with O(1) extra space.

class Solution {
	public int smallestDivisor(int[] nums, int threshold) {
		int dMin = 1;
		int dMax = 0;

		for (int n : nums) {
			dMax = Math.max(dMax, n);
		}

		while (dMin < dMax) {
			int dMid = (dMin + dMax) / 2;

			if (isBelowThreshold(nums, threshold, dMid)) {
				dMax = dMid;
			} else {
				dMin = 1 + dMid;
			}
		}

		return dMin;
	}

	private boolean isBelowThreshold(int[] nums, int threshold, int d) {
		long total = 0;

		for (int n : nums) {
			total += (n + d - 1) / d;
		}

		return total <= threshold;
	}
}

import math
from typing import List

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def isBelowThreshold(d):
            total = 0
            for n in nums:
                total += math.ceil(n/d)

            return total <= threshold

        d_min, d_max = 1, max(nums)
        while d_min < d_max:
            d_mid = (d_min+d_max)//2

            if isBelowThreshold(d_mid):
                d_max = d_mid
            else:
                d_min = 1 + d_mid

        return d_min

410. Split Array Largest Sum

Binary search the maximum allowed subarray sum from max(nums) through sum(nums). For each candidate, greedily count how many subarrays are needed when no subarray may exceed that sum. A larger candidate can only require the same number or fewer subarrays, so feasibility is monotonic. The runtime is O(n log(sum(nums))) with O(1) extra space.

class Solution {
	public int splitArray(int[] nums, int k) {
		int minS = 0;
		int maxS = 0;

		for (int num : nums) {
			minS = Math.max(minS, num);
			maxS += num;
		}

		while (minS < maxS) {
			int midS = minS + (maxS - minS) / 2;

			if (checkSum(nums, k, midS) == false) {
				minS = midS + 1;
			} else {
				maxS = midS;
			}
		}

		return minS;
	}

	private boolean checkSum(int[] nums, int k, int target) {
		int count = 0;
		int subTotal = 0;

		for (int num : nums) {
			subTotal += num;
			if (subTotal == target) {
				count++;
				subTotal = 0;
			} else if (subTotal > target) {
				count++;
				subTotal = num;
			} else {
				continue;
			}
		}

		if (subTotal > 0) {
			count++;
		}

		return count <= k;
	}
}

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        # for each target_sum, we check if it is feasible to divide nums
        # into k subarray and each subarray sum is less than target_sum
        # we can perform this check in O(N)
        def checkSum(target):
            count = 0
            sub_total = 0

            for num in nums:
                sub_total += num
                if sub_total == target:
                    count += 1
                    sub_total = 0
                elif sub_total > target:
                    count += 1
                    sub_total = num
                else:
                    continue

            if sub_total:
                count += 1

            return count <= k

        min_s, max_s = max(nums), sum(nums)

        while min_s < max_s:
            mid_s = (min_s + max_s) // 2

            if checkSum(mid_s) == False:
                min_s = mid_s + 1
            else:
                max_s = mid_s

        return min_s

4. Median of Two Sorted Arrays

Find the median without merging the arrays. Binary search the last index taken from the shorter array and derive the corresponding index in the other array. Use negative and positive infinity at partition boundaries. When both left values are no greater than the opposite right values, the partition is valid and directly yields the median. This takes O(log(min(m, n))) time and O(1) extra space.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int N1 = nums1.length;
        int N2 = nums2.length;
        if (N1 > N2){
            return findMedianSortedArrays(nums2, nums1);
        }

        int L = (N1 + N2)/2;
        int left = -1;
        int right = N1 - 1;

        while (true){
            int mid1 = (left + right)/2;
            int mid2 = L - mid1 - 2;

            int n1_left = (mid1 >= 0) ? nums1[mid1] : Integer.MIN_VALUE;
            int n1_right = (mid1 + 1 < N1) ? nums1[mid1+1] : Integer.MAX_VALUE;
            int n2_left = (mid2 >= 0) ? nums2[mid2] : Integer.MIN_VALUE;
            int n2_right = (mid2 + 1 < N2) ? nums2[mid2+1] : Integer.MAX_VALUE;

            if (n1_left <= n2_right && n2_left <= n1_right){
                if ( (N1 + N2) % 2 == 1){
                    return Math.min(n1_right, n2_right);
                } else {
                    return 0.5*(Math.max(n1_left, n2_left)+Math.min(n1_right, n2_right));
                }
            } else if (n1_left > n2_right){
                right = mid1 - 1;
            } else {
                left = mid1 + 1;
            }
        }
    }
}

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        N1, N2 = len(nums1), len(nums2)
        if N1 > N2:
            return self.findMedianSortedArrays(nums2, nums1)

        L = (N1+N2)//2
        # binary search on the shorter array
        left, right = 0, N1-1 # both are in range
        while True: # must be True
            mid1 = (left + right)//2
            mid2 = L - mid1 - 2
            # we may take 0 elements from nums1 or all elements from nums1 --> mid1 = -1 or mid1 = N1-1
            n1_left = nums1[mid1] if mid1 >= 0 else float('-inf')
            n1_right = nums1[mid1+1] if mid1+1 < N1 else float('inf')
            # we may take 0 elements from nums2 or all elements from nums2
            n2_left = nums2[mid2] if mid2 >= 0 else float('-inf')
            n2_right = nums2[mid2+1] if mid2+1 < N2 else float('inf')

            if n1_left <= n2_right and n2_left <= n1_right:
                if (N1+N2) % 2 == 1:
                    return min(n1_right, n2_right)
                else:
                    return 0.5*(max(n1_left, n2_left)+min(n1_right, n2_right))
            elif n1_left > n2_right: # too many elements in left half of nums1
                right = mid1 - 1 # must have -1
            else:
                left = mid1 + 1 # must have +1