Binary Search on Sorted Data

Binary search is not guessing the middle. It is a proof that half of the remaining search space cannot contain the answer. That proof depends on sorted data, a correct invariant, and careful boundary movement.

The Interval Invariant

At every step, binary search keeps an interval that may still contain the answer. Compare the middle value with the target, then discard the half that cannot contain a valid answer. If the boundaries do not shrink, the loop can run forever.

Scenario: Finding an Event in a Sorted Log

A monitoring system stores event timestamps in ascending order. When an incident starts at 14:03, engineers need the first event at or after that time. Exact search is not enough; they need the lower bound insertion point.

Same Pattern in Java, Python, and JavaScript

Lower bound returns the first index whose value is greater than or equal to target. If every value is smaller, it returns nums.length.

class LowerBound {
    static int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

Boundary Bugs Engineers Actually Make

• Using `while (left <= right)` with lower-bound boundary updates from `while (left < right)`.
• Setting `right = mid - 1` when the mid value could still be the first valid answer.
• Computing mid as `(left + right) / 2` in languages where large integer addition can overflow.
• Returning `mid` after the loop instead of the converged boundary.
• Ignoring duplicate values when the prompt asks for first or last occurrence.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the index where target exists or should be inserted in sorted order.
• Return the first and last index of target in a sorted array.
• Find target in a rotated sorted array with distinct values.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class LowerBoundAnswer {
    static int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

class SearchRange {
    static int[] range(int[] nums, int target) {
        int first = lower(nums, target);
        int after = lower(nums, target + 1);
        if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
        return new int[]{first, after - 1};
    }
    static int lower(int[] nums, int target) { int l = 0, r = nums.length; while (l < r) { int m = l + (r - l) / 2; if (nums[m] < target) l = m + 1; else r = m; } return l; }
}

class RotatedSearch { static int search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int m = l + (r - l) / 2; if (nums[m] == target) return m; if (nums[l] <= nums[m]) { if (nums[l] <= target && target < nums[m]) r = m - 1; else l = m + 1; } else { if (nums[m] < target && target <= nums[r]) l = m + 1; else r = m - 1; } } return -1; } }

Solved modelWorked Interview Answer

Return the first index whose value is greater than or equal to target. Lower bound keeps the first possible answer inside [left, right). When nums[mid] is already valid, move right to mid instead of discarding it.

class LowerBoundAnswer {
    static int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Mixing inclusive and exclusive boundary templates.
• Moving right past a possible answer in lower bound.
• Returning mid after the loop.
• Ignoring duplicates when first occurrence is required.
• Not proving sorted or monotonic structure.

Execution guardrailQuick-Start Checklist

• Define the invariant.
• Choose inclusive or half-open interval.
• Compute mid safely.
• Move boundaries so the interval shrinks.
• Return the converged boundary.
• Test empty, one item, no match, and duplicate cases.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice search insert position, first/last occurrence, and rotated sorted array later.
• Review database B-tree indexes conceptually.
• Compare binary search templates before memorizing code.