Binary Search: Range and Boundary Analysis

These problems focus on the precision required to implement "Left Boundary" and "Right Boundary" searches correctly.

Find First and Last Position of Element (LeetCode 34)

Commonly known as searchRange, this problem requires finding both the starting and ending indices of a target value.

public int[] searchRange(int[] nums, int target) {
    int start = findBound(nums, target, true);
    if (start == -1) return new int[]{-1, -1};
    int end = findBound(nums, target, false);
    return new int[]{start, end};
}

private int findBound(int[] nums, int target, boolean isFirst) {
    int n = nums.length;
    int begin = 0, end = n - 1;
    int result = -1;

    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] == target) {
            result = mid; // Potential match found
            if (isFirst) {
                end = mid - 1; // Keep looking left for the 'first'
            } else {
                begin = mid + 1; // Keep looking right for the 'last'
            }
        } else if (nums[mid] < target) {
            begin = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}

Find Peak Element (LeetCode 162)

A peak element is an element that is strictly greater than its neighbors.

Logic: Compare mid with its right neighbor. If mid < mid + 1, we are on an "upward slope," and a peak must exist to the right. Otherwise, the peak is at mid or to its left.

public int findPeakElement(int[] nums) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[mid + 1]) {
            // Downward slope: peak is at mid or to the left
            high = mid;
        } else {
            // Upward slope: peak is guaranteed to the right
            low = mid + 1;
        }
    }
    return low;
}

Search Insert Position (LeetCode 35)

Find where target should be inserted. This is conceptually identical to finding the Left Boundary (the first element $\ge$ target).

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length; // Note: right is length, not length-1
    while (left < right) {
        int mid = left + (left - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

Counting Occurrences

You can use the difference between the Right Boundary and the Left Boundary to count how many times a value appears:

int count = findBound(nums, target, false) - findBound(nums, target, true) + 1;
// If findBound returns -1, handle count as 0.

Patterns Summary Table