Binary Search | Algorithms & Data Structures

Algorithm Summary

Binary search locates a target in a sorted search space by discarding half of the remaining candidates after every comparison. It is a natural fit for sorted arrays, but not for linked lists because indexed access is not constant time.

Java

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

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

The template above uses a closed interval, [left, right], so the loop condition is left <= right.

Examples

Binary Search — LC 704

The base pattern: return the position of a target in an ascending array. The closed-interval template applies directly.

First Bad Version — LC 278

Search for the first index that satisfies a monotonic predicate. When mid is good, discard it and everything before it; when it is bad, keep it as a candidate by moving right to mid - 1. At termination, left is the first bad version.

Java

int left = 1;
int right = n;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (!isBadVersion(mid)) left = mid + 1;
    else right = mid - 1;
}
return left;

Sqrt(x) — LC 69

Search for the largest integer whose square does not exceed x. Cast before multiplication to avoid integer overflow.

Java

int left = 0;
int right = x;
while (left <= right) {
    int mid = left + (right - left) / 2;
    long square = (long) mid * mid;
    if (square == x) return mid;
    if (square < x) left = mid + 1;
    else right = mid - 1;
}
return right;

Find First and Last Position of Element in Sorted Array — LC 34

Run a boundary-aware binary search twice. After finding the target, continue toward the left for the first position and toward the right for the last position.

Java

private int boundary(int[] nums, int target, boolean findLeft) {
    int left = 0;
    int right = nums.length - 1;
    int result = -1;

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

Median of Two Sorted Arrays — LC 4

Binary-search a partition in the shorter array and derive the matching partition in the longer array. A valid partition places every value on the left at or below every value on the right.

Two boundary details matter:

Use j = (m + n + 1) / 2 - i so the left partition receives the extra item when the total length is odd.
Use right = nums1.length, not nums1.length - 1, because a partition may sit after the final element.

Java

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

    int m = nums1.length;
    int n = nums2.length;
    int left = 0;
    int right = m;

    while (left <= right) {
        int i = left + (right - left) / 2;
        int j = (m + n + 1) / 2 - i;

        int left1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int right1 = i == m ? Integer.MAX_VALUE : nums1[i];
        int left2 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int right2 = j == n ? Integer.MAX_VALUE : nums2[j];

        if (left1 <= right2 && left2 <= right1) {
            if ((m + n) % 2 == 1) return Math.max(left1, left2);
            return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
        }
        if (left1 > right2) right = i - 1;
        else left = i + 1;
    }
    throw new IllegalArgumentException("Input arrays must be sorted");
}