Binary Search

Binary search cuts the search space in half at every step by comparing the midpoint to the target, discarding the side that cannot contain the answer.

• Replaces O(n) linear scan with O(log n) by exploiting sorted or monotonic structure
• Four modes: find exact target, first occurrence, last occurrence, or search over an answer space
• Reach for it when input is sorted, when you're minimizing or maximizing over a range, or when you can write a yes/no feasibility check

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of binary search patterns.

Practice Tips

How to Identify a Binary Search Problem

• The input array is sorted, or you can sort it first
• You're looking for an exact value, or a first or last occurrence
• You're minimizing or maximizing something over a numeric range
• The answer has a monotonic property: if X works, then all larger (or smaller) values also work
• The problem says "find the minimum X such that..." or "find the k-th smallest..."

Binary Search vs. Other Techniques

Interview Approach

1. Ask: is the input sorted, or can I binary search over an answer space?
2. Decide the pattern: exact match, left boundary, right boundary, or answer space
3. Choose the loop condition: left <= right when you always move by at least 1 (mid+1 or mid-1); left < right when you assign right = mid — otherwise two-element arrays loop forever
4. Set boundaries: for answer space, define the realistic minimum and maximum values
5. Determine what to return: left converges to the answer in boundary and answer space searches
6. Watch for: integer overflow in mid calculation, off-by-one on boundaries, and right = mid (not mid - 1) in boundary searches

4 Main Patterns

Pattern 1: Standard — Find Exact Target

Copy
int left = 0;
int right = array.length - 1;

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

Pattern 2: Left Boundary — First Occurrence

Copyint left = 0;
int right = array.length - 1;
int result = -1;

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

Pattern 3: Right Boundary — Last Occurrence

Copyint left = 0;
int right = array.length - 1;
int result = -1;

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

Pattern 4: Answer Space Search — Minimize or Maximize

Copyint left = minPossibleAnswer;
int right = maxPossibleAnswer;

while (left < right) {
    int mid = left + (right - left) / 2;
    if (feasible(mid)) {
        right = mid;    // try smaller (minimize)
    }
    else {
        left = mid + 1; // need larger
    }
}
return left;

Problem 1: Classic Binary Search ⭐ MUST DO

Find the index of target in a sorted array. Return -1 if not found.

Example:

CopyInput:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Solution:

Copypublic 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;
        } else if (nums[mid] < target) {  
            left = mid + 1;
        } else {                          
            right = mid - 1;
        }
    }
    return -1;
}

Complexity:

Real World: Searching a sorted product catalog by SKU — given millions of sorted IDs, binary search finds any entry in ~20 comparisons instead of ~1,000,000. Also used in dictionary lookups, sorted log file searches, and database index scans.

Variations:

1. Return insertion point when not found — instead of returning -1, return left when the loop ends. left always lands at the position where target would be inserted to keep the array sorted.
2. Binary search on a 2D matrix — treat the m×n matrix as a flat sorted array; convert 1D index with row = mid / n, col = mid % n. Same exact/match logic.

Interview Disguises:

• "A dictionary stores words in alphabetical order. Check if a given word exists and return its position." — sorted array, find exact value = standard binary search.
• "A server log has millions of entries sorted by timestamp. Find the entry for a specific timestamp, or return -1 if it doesn't exist." — sorted array lookup; timestamps are the keys.

Problem 2: First Bad Version

Given n versions, find the first bad version. All versions after the first bad version are also bad.

Example:

CopyInput:  n = 5, bad = 4
Output: 4  (versions 4 and 5 are bad; 4 is the first)

Solution:

Copypublic int firstBadVersion(int n) {
    int left = 1, right = n, result = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            result = mid;       // Record potential answer
            right = mid - 1;   // Search left for earlier bad version
        } else {
            left = mid + 1;
        }
    }
    return result;
}

Complexity:

Real World: Git bisect — finding the first commit that introduced a bug by running a test suite as the yes/no oracle. The same left-boundary pattern drives automated bisection in CI/CD pipelines: all versions before the bad one pass, all after fail.

Variations:

1. First true in a boolean array — same pattern with a direct array lookup instead of an API call. The condition flips from isBadVersion(mid) to arr[mid] == true.
2. First day a condition is met — e.g., first day stock price exceeds a threshold in a sorted historical dataset. Same monotonic boolean sequence; API call becomes an array comparison.

Interview Disguises:

• "A deployment pipeline runs builds numbered 1 to N. Once a build breaks, all subsequent builds also break. Find the first broken build number." — first bad version exactly; build numbers replace version numbers.
• "A feature flag is rolled out progressively by user rank — once enabled at rank R it is on for all ranks above R. Find the minimum rank where the flag is active." — first true in a monotonic boolean sequence = left boundary binary search.

Problem 3: Sqrt(x)

Compute the integer square root of x, rounded down to the nearest integer. Do not use any built-in exponent functions.

Example:

CopyInput:  x = 8
Output: 2  (sqrt(8) = 2.82..., floor = 2)

Input:  x = 4
Output: 2

Solution:

Copypublic int mySqrt(int x) {
    if (x == 0 || x == 1) {
        return x;
    }
    int left = 1, right = x, result = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mid <= x / mid) {  // Division avoids overflow (no mid*mid)
            result = mid;      // Record: mid^2 <= x
            left = mid + 1;    // Try larger
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Complexity:

Real World: Embedded systems without a floating-point unit computing integer square roots for sensor distance calculations or image scaling. Also used in game engines to compute grid dimensions given a total tile count.

Variations:

1. Integer cube root — same right boundary pattern; change the condition to (long) mid * mid * mid <= x. Cast to long to avoid overflow.
2. Largest k such that k² ≤ n — same problem, different framing. Confirms you understand the right boundary pattern: record mid whenever mid*mid <= x, keep searching right for a larger valid answer.

Interview Disguises:

• "An embedded sensor device has no floating-point unit. Compute the integer square root of a raw distance reading without using Math.sqrt()." — Sqrt(x) exactly; hardware constraint is the framing.
• "A square grid game needs the largest square board that fits within a given number of cells n. Return the side length." — largest k where k² ≤ n = floor(sqrt(n)) = this problem.

Problem 4: Find First and Last Position of Element

Given a sorted array, find the starting and ending position of a target value. Return [-1, -1] if not found.

Example:

CopyInput:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Input:  nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Key Insight:

• Run two independent binary searches: one for the leftmost occurrence, one for the rightmost
• Left boundary: when nums[mid] >= target, record mid and narrow right to search further left
• Right boundary: when nums[mid] <= target, record mid and narrow left to search further right

Solution:

Copy
public int[] searchRange(int[] nums, int target) {
    int[] result = {-1, -1};
    
    result[0] = findLeft(nums, target);
    if (result[0] == -1) {
        return result;  // Skip right search if not found
    }
    
    result[1] = findRight(nums, target);
    return result;
}

private int findLeft(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            if (nums[mid] == target) {
                result = mid;
            }
            right = mid - 1;   // Keep searching left
        } else {
            left = mid + 1;
        }
    }
    return result;
}

private int findRight(int[] nums, int target) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            if (nums[mid] == target) {
                result = mid;
            }
            left = mid + 1;    // Keep searching right
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Complexity:

Real World: Finding the date range of a specific error code in a sorted server log — first occurrence is when the incident started, last occurrence is when it ended. Also used in inventory systems to find the shelf range occupied by a given SKU.

Variations:

1. Count occurrences — once you have first and last positions, count = last - first + 1. No extra code needed beyond this problem's solution.
2. First and last position in a rotated array — combine the rotation check from Problem 5 with the left/right boundary logic. Significantly harder; tests composition of two patterns.

Interview Disguises:

• "A sorted server log records error codes. Find the timestamp of the first and last occurrence of error code 404 to determine incident duration." — find first and last position; error codes are the target.
• "An inventory system assigns sorted SKU codes to shelf slots. Find the first and last shelf slot occupied by a given product SKU." — same left + right boundary binary search; shelf slots are the array.

Problem 5: Search in Rotated Sorted Array ⭐ MUST DO [B75-33]

A sorted array was rotated at an unknown pivot. Search for target and return its index, or -1 if not found.

Example:

CopyInput:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

Key Insight:

• At every midpoint, one of the two halves is always fully sorted
• Check if the left half is sorted (nums[left] <= nums[mid]), then check if target falls inside that range
• If target is not in the sorted half, search the other half

Solution:

Copypublic int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }

        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;  // Target in sorted left half
            } else {
                left = mid + 1;   // Target must be in right half
            }
        }
        // Right half is sorted
        else {
            if (nums[right] >= target && target > nums[mid]) {
                left = mid + 1;   // Target in sorted right half
            } else {
                right = mid - 1;  // Target must be in left half
            }
        }
    }
    return -1;
}

Complexity:

Real World: Searching a ring buffer (circular buffer) for a specific value — data is stored in sorted order but wraps around. Also used in circular scheduling systems where task IDs are assigned in sorted order starting from an arbitrary point.

Variations:

1. Search Rotated with Duplicates (LC 81) — when nums[left] == nums[mid], you can't determine which half is sorted; fall back to left++ to shrink the ambiguous boundary. Worst case degrades to O(n).
2. Count rotations — the number of times the array was rotated equals the index of the minimum element. Use findPivot() from Problem 10 — same logic; the index it returns is the rotation count.

Interview Disguises:

• "A circular request log stores request IDs in sorted order but starts writing from an arbitrary position. Find if a specific request ID exists in the log." — rotated sorted array search; request IDs are the values.
• "Employee IDs are assigned sequentially but the HR database starts its index from the most recently hired employee. Find a specific employee's record." — sorted data with a circular offset = rotated array search.

Problem 6: Find Peak Element

A peak element is strictly greater than its neighbors. Find any peak index. Treat out-of-bounds elements as negative infinity.

Example:

CopyInput:  nums = [1, 2, 3, 1]
Output: 2  (nums[2] = 3 is a peak)

Input:  nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5  (nums[5] = 6 is a peak)

Key Insight:

• Always move toward the increasing slope: if nums[mid] < nums[mid + 1], a peak must exist to the right
• The out-of-bounds boundary condition guarantees every half that goes up must contain a peak

Solution:

Copypublic int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;  // Peak in right half
        }
        else {
            right = mid;      // Peak at mid or left
        }
    }
    return left;
}

Complexity:

Real World: Signal processing — finding any local maximum in a sensor reading array to detect antenna peaks or resonance frequencies. Also used in terrain analysis to find hilltops in an elevation profile for tower placement.

Variations:

1. Find Peak in 2D Matrix (LC 1901) — binary search on columns: for each mid column, find the row with the maximum value, then check neighbors left and right to decide which half to recurse into. O(m log n).
2. Find all peaks — binary search only finds one peak. Finding all peaks requires a linear scan (O(n)); no way to prune halves when multiple peaks exist.

Interview Disguises:

• "A sensor array records signal strength at each antenna position. Find any position where signal strength is greater than both its neighbors — this is a candidate peak for tower placement." — find peak element; signal strengths are the array values.
• "A trading algorithm scans intraday prices and needs any local price maximum to trigger a sell order — it doesn't need the global max, just a local one." — find any peak = this problem; prices are the array.

Problem 7: Koko Eating Bananas ⭐ MUST DO

Koko must eat all banana piles within h hours. Find the minimum integer eating speed k (bananas per hour) that lets her finish in time.

Example:

CopyInput:  piles = [3, 6, 7, 11], h = 8
Output: 4

Input:  piles = [30, 11, 23, 4, 20], h = 5
Output: 30

Key Insight:

• Answer space: minimum speed is 1, maximum is the largest pile (eating one pile per hour is always enough)
• Monotonic property: if speed k works, then k+1 also works — so binary search on speed
• Feasibility check: hours needed for a pile at speed k is ceil(pile / k) = (pile + k - 1) / k

Solution:

Copypublic int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = 0;
    
    for (int pile : piles) {
        right = Math.max(right, pile);
    }

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, mid, h)) {
            right = mid;    // Try slower
        }
        else {
            left = mid + 1; // Need faster
        }
    }
    return left;
}

private boolean canFinish(int[] piles, int speed, int h) {
    int hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed;  // Ceiling division
        if (hours > h) {
            return false;           // Early exit
        }
    }
    return true;
}

Complexity:

Real World: Rate limiting — finding the minimum request processing rate such that all queued requests are handled within a time window. Also used in bandwidth allocation to find the minimum bitrate that streams all media files within a deadline.

Variations:

1. Capacity to Ship Packages (LC 1011) — same answer space pattern; feasibility check is a greedy simulation (load packages in order, start new day when over capacity) instead of ceiling division. Direct structural transfer.
2. Split Array Largest Sum (LC 410) — minimize the maximum subarray sum when splitting into k parts. Same binary search on answer space; feasibility check asks whether you can split into ≤ k parts with each part ≤ mid.

Interview Disguises:

• "A rate limiter must process all queued API requests within a time window. Find the minimum processing rate (requests per second) to clear the entire queue before the window closes." — Koko exactly; pile sizes are queue lengths per second slot, h is the time window.
• "A printer queue has jobs with known page counts. Find the minimum pages-per-minute speed to finish all jobs before a deadline." — ceiling division feasibility check on a sorted-by-deadline job list = Koko with different domain names.

Problem 8: Search a 2D Matrix

Search for a target in an m × n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row.

Example:

CopyInput:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Input:  matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Key Insight:

• The matrix is a sorted 1D array laid out row by row — treat it as one
• Convert 1D index to 2D: row = index / cols, col = index % cols
• Binary search on the virtual 1D array in O(log(m × n))

Solution:

Copypublic boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int val = matrix[mid / n][mid % n];  // 1D index → 2D coordinates
        if (val == target) {
            return true;
        }
        else if (val < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return false;
}

Complexity:

Real World: Searching a sorted 2D lookup table — tax bracket matrices, pricing grids, or truth tables where each row continues from where the previous ended. Also used in game engines to search sorted tile maps.

Variations:

1. Search a 2D Matrix II (LC 240) — rows sorted left-to-right, columns sorted top-to-bottom, but rows do NOT continue into the next row. Different algorithm: start at top-right corner, move left if too large, move down if too small. O(m + n) instead of O(log(m×n)).
2. Count negatives in a sorted matrix — binary search each row to find the boundary between non-negative and negative values, then sum up. O(m log n).

Interview Disguises:

• "A tax system stores bracket rates in a sorted 2D grid where each row continues from the end of the previous row. Check whether a specific taxable income value appears in the table." — search 2D matrix; income values are stored in row-major sorted order.
• "A game map stores tile IDs in sorted order row by row, with each row starting after the last tile of the previous row. Find if a specific tile type is present." — 1D-to-2D index mapping + standard binary search = this problem.

Problem 9: Find K-th Smallest Pair Distance

Given an integer array, find the k-th smallest distance among all pairs. Distance is the absolute difference between two elements.

Example:

CopyInput:  nums = [1, 3, 1], k = 1
Output: 0  (distance between the two 1s)

Input:  nums = [1, 6, 1], k = 3
Output: 5

Key Insight:

• Answer space: minimum distance is 0, maximum is max - min after sorting
• Binary search on distance D: how many pairs have distance ≤ D? Use a two-pointer sweep in O(n)
• If the count of pairs with distance ≤ D is ≥ k, the answer is at most D — classic left boundary search

Solution:

Copypublic int smallestDistancePair(int[] nums, int k) {
    Arrays.sort(nums);
    int left = 0, right = nums[nums.length - 1] - nums[0];
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (countPairs(nums, mid) >= k) {
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

private int countPairs(int[] nums, int maxDist) {
    int count = 0, lo = 0;
    for (int hi = 1; hi < nums.length; hi++) {
        while (nums[hi] - nums[lo] > maxDist) {
            lo++;
        }
        count += hi - lo;  // All pairs (lo..hi-1, hi) have distance <= maxDist
    }
    return count;
}

Complexity:

Real World: Quality control — finding the k-th smallest measurement difference between any two parts in a production batch to set a percentile tolerance threshold. Also used in network monitoring to find the k-th smallest latency difference between server pairs.

Variations:

1. K-th smallest element in a sorted matrix (LC 378) — same answer space + count approach; instead of counting pairs with distance ≤ mid, count matrix elements ≤ mid using a staircase scan. Same binary search shell.
2. K-th largest pair sum — mirror of this problem: binary search on the sum value, count pairs with sum ≤ mid using two pointers. Flip >= k to <= k and adjust boundary direction.

Interview Disguises:

• "A manufacturing QC system measures component lengths. Find the k-th smallest difference between any two components — this sets the k-th percentile tolerance threshold." — k-th smallest pair distance; component measurements are the array.
• "A network operations tool records round-trip times between all server pairs. Find the k-th smallest RTT difference to configure an alerting threshold at the k-th percentile." — binary search on distance value + two-pointer count = this problem.

Problem 10: Pair Sum in Rotated Sorted Array ⭐ MUST DO [B75-153]

Given a rotated sorted array with unique elements and an integer target, return true if any two elements sum to target.

Example:

CopyInput:  nums = [11, 15, 6, 8, 9, 10], target = 16
Output: true   (6 + 10 = 16)

Input:  nums = [4, 5, 1, 2, 3], target = 6
Output: true   (4 + 2 = 6  or  5 + 1 = 6)

Input:  nums = [11, 15, 6, 8, 9, 10], target = 45
Output: false

Key Insight:

• This problem is built from two sub-problems stacked together:
  1. Find Minimum in Rotated Sorted Array [B75-153] — binary search finds the pivot (index of the smallest element). This is a standalone Blind 75 problem embedded here as findPivot().
  2. Two-pointer with circular indexing — start one pointer at the minimum (smallest) and the other just before it circularly (the largest); converge using modulo wrap-around.
• Naive pivot approach: linear scan for the drop point (nums[i] > nums[i+1]) is O(n) time, O(1) space. Binary search does it in O(log n) time, O(1) space — same space, better time.
• findPivot compares nums[mid] with nums[right] (not nums[left]): if nums[mid] > nums[right] the drop is right of mid; otherwise minimum is at mid or left. Comparing with nums[left] breaks on 2-element arrays where left == mid.
• Circular pointer arithmetic: advance low with (low + 1) % n, retreat high with (n + high - 1) % n — adding n before subtracting prevents negative modulo.

Solution:

Copypublic boolean hasPairWithSum(int[] nums, int target) {
    int n = nums.length;
    if (n < 2) {
        return false;
    }

    // Step 1: find pivot — Find Minimum in Rotated Sorted Array [B75-153]
    int pivot = findPivot(nums);

    // Step 2: two-pointer from smallest to largest, wrapping with modulo
    int low = pivot;                  // smallest element
    int high = (pivot - 1 + n) % n;  // largest element (just before pivot, circularly)

    while (low != high) {
        int sum = nums[low] + nums[high];
        if (sum == target) {
            return true;
        }
        if (sum < target) {
            low = (low + 1) % n;       // need larger: move low forward
        } else {
            high = (n + high - 1) % n; // need smaller: move high backward
        }
    }
    return false;
}

// Find Minimum in Rotated Sorted Array [B75-153]
// Returns the index of the minimum element (the pivot / rotation point)
private int findPivot(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1; // minimum is in right half
        } else {
            right = mid;    // minimum is at mid or left
        }
    }
    return left; // index of the minimum element
}

Complexity:

Real World: Finding two offsetting transactions in a circular financial ledger — amounts are stored in sorted order but the ledger starts from an arbitrary entry point. The findPivot step is used on its own in circular buffers and ring queues to locate the oldest entry (the logical start of the buffer).

Variations:

1. Pair sum in regular sorted array — Two Sum II: same two-pointer logic with no pivot step. Shows exactly what findPivot() eliminates when there is no rotation.
2. Find Minimum with Duplicates (LC 154) — inside findPivot, when nums[mid] == nums[right] you can't tell which side the minimum is on; do right-- to shrink safely. Worst case O(n).
3. Three sum in rotated sorted array — call findPivot() to unwrap, then apply 3Sum logic using circular pointer arithmetic. The pivot step is identical; only the inner loop changes.

Interview Disguises:

• "A circular transaction ledger stores debit/credit amounts in sorted order but starts recording from an arbitrary month. Find two transactions that together net to zero for reconciliation." — pair sum in rotated array; transaction amounts are the values, target is 0.
• "A sensor ring buffer records calibration readings in sorted order but wraps around. Find two readings that sum to a known calibration target to verify sensor alignment." — find pivot to unwrap the circular order, then two-pointer = this problem.
• "A circular queue stores network packets with increasing sequence numbers but wraps around. Find the sequence number of the oldest packet." — this is findPivot() alone; the standalone B75-153 sub-problem inside this solution.

Quick Reference Table

When to Use Each Pattern

Standard Binary Search

• Sorted array and you're looking for an exact value
• Need to find where a value would be inserted in sorted order
• Matrix where rows are sorted and each row starts after the previous ends

Left Boundary (First Occurrence)

• Find the first index where a condition becomes true
• Problems with "earliest", "first", or "minimum index"
• Smallest valid answer in a range (Koko eating speed, ship capacity)

Right Boundary (Last Occurrence)

• Find the last index where a condition is still true
• Problems with "latest", "last", or "maximum index"
• Largest valid answer in a range (Sqrt)

Answer Space Search

• Not searching an array index, but a range of numeric values
• You can write a yes/no feasibility function
• Monotonic property: if X is feasible, all values above (or below) X are also feasible
• Keywords: "minimum capacity/speed/size such that..." or "k-th smallest..."

Modified Standard (Rotated Arrays)

• Input is a sorted array rotated at an unknown pivot
• One half is always fully sorted — use that to decide where to search
• Apply when finding a value (Search in Rotated) or the minimum (Find Minimum Rotated)

Common Mistakes to Avoid

General Binary Search Mistakes

1. Integer overflow in mid: always use left + (right - left) / 2, never (left + right) / 2
2. Infinite loop: when using left <= right, always move to mid + 1 or mid - 1, never just mid
3. Wrong loop condition: use left <= right when every branch moves by at least 1 (mid+1 or mid-1); use left < right when you assign right = mid — the condition prevents an infinite loop on two-element arrays where left == mid
4. Wrong return value: for boundary and answer space searches, return left — both pointers converge to the answer

Boundary Search Mistakes

5. Forgetting the result variable: in left/right boundary searches you need a separate result variable to store the best answer before narrowing the range
6. Using right = mid - 1 instead of right = mid: when right = mid, you must use left < right — otherwise two-element arrays loop forever
7. Swapping update directions: left boundary narrows right (right = mid - 1); right boundary narrows left (left = mid + 1)

Rotated Array Mistakes

8. Comparing with left instead of right in Find Minimum: nums[left] changes as you search and loses track of the rotation — always compare nums[mid] with nums[right]
9. Missing the = in nums[left] <= nums[mid]: the equal sign handles the two-element case where left == mid, preventing an infinite loop

Answer Space Search Mistakes

10. Wrong minimum boundary: for Koko, minimum speed is 1, not 0 — speed 0 causes division by zero
11. Using integer division instead of ceiling: hours for a pile at speed k is (pile + k - 1) / k, not pile / k
12. Not verifying the monotonic property: confirm that if X is feasible, all values above X are also feasible before applying answer space binary search