🔍 Binary Search

The night-before sheet: find the yes/no check, pick first or last, write your Style A.

💭 Your own rules: DSA thoughts → Binary Search, Must Remember. Each section below links the ones that apply.

✍️ The code follows your Style A from BS #1, but it isn't your own LeetCode code yet. As you solve each problem, send your solution and it replaces the one here.

🧠 0 · How to think

"Guess the middle. The answer tells you which half to throw away."

Binary search is not really about sorted arrays. It works whenever you can ask a yes/no question about a position (or a value) and the answer flips only once: all ✗ then all ✓, or all ✓ then all ✗.

🧭 1 · Spot it

🧭 Size hint: answers up to 10⁹ and an O(n) check → about 30 checks, O(n log 10⁹). That's usually what the constraints are pointing at.

📐 2 · The three templates

"Exact: low <= high. First that works: high = mid. Last that works: low = mid, round up."

🔍 704 · Binary Search (exact match) ⏱️ O(log n) · 📦 O(1)

💡 while(low <= high), and mid ± 1 on both sides because mid was already checked.

// 🔍 BINARY SEARCH (exact match)
function search(nums: number[], target: number): number {
    let low = 0;
    let high = nums.length - 1; // the answer must be inside, so n - 1

    while(low <= high) {
        const mid = (low + high) >> 1;

        if(nums[mid] === target) return mid;
        else if(nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }

    return -1;
};

⬅️ 35 · Search Insert Position (first that works) ⏱️ O(log n) · 📦 O(1)

💡 First index with nums[i] ≥ target. If every value is smaller, low lands on the extra slot n, which is exactly the insert position.

// 🚧 SEARCH INSERT POSITION (LEFT: first index with nums[i] >= target)
function searchInsert(nums: number[], target: number): number {
    let low = 0;
    let high = nums.length; // extra slot: bigger than everything → n

    while(low < high) {
        const mid = (low + high) >> 1; // round DOWN

        if(nums[mid] >= target) high = mid; // works → answer is mid or left of it
        else low = mid + 1;
    }

    return low; // low === high === the answer
};

➡️ 69 · Sqrt(x) (last that works) ⏱️ O(log n) · 📦 O(1)

💡 Last x with x * x ≤ n. low = mid, so mid must round up: with two left, round down picks low again and the loop never ends.

// 🚧 SQRT(x) (RIGHT: last x with x * x <= n)
function mySqrt(x: number): number {
    let low = 0; // 0 * 0 <= x always works, so no -1 slot needed
    let high = x;

    while(low < high) {
        // round UP. x can be 2³¹ − 1, so low + high + 1 passes 2³¹ and ">> 1" turns negative
        const mid = Math.floor((low + high + 1) / 2);

        if(mid * mid <= x) low = mid; // works → answer is mid or right of it
        else high = mid - 1;
    }

    return low;
};

Style B (ans = mid inside the loop, low <= high) gives the same answers. Your BS #1 keeps it only for reading other people's code; write Style A.

🚧 3 · Boundary: first / last, insert, peak

"Not 'where is x?' but 'where does ✗ turn into ✓?'"

🚧 34 · First and Last Position ⏱️ O(log n) · 📦 O(1)

💡 One LEFT search (first ≥ target) and one RIGHT search (last ≤ target). After the first one, check you really found the target.

// 🚧 FIRST AND LAST POSITION (one LEFT search + one RIGHT search)
function searchRange(nums: number[], target: number): number[] {
    const n = nums.length;

    // first index with nums[i] >= target
    let low = 0;
    let high = n;
    while(low < high) {
        const mid = (low + high) >> 1;
        if(nums[mid] >= target) high = mid;
        else low = mid + 1;
    }
    if(low === n || nums[low] !== target) return [-1, -1]; // landed on the extra slot, or not the target
    const first = low;

    // last index with nums[i] <= target
    low = -1;
    high = n - 1;
    while(low < high) {
        const mid = (low + high + 1) >> 1; // round UP
        if(nums[mid] <= target) low = mid;
        else high = mid - 1;
    }

    return [first, low];
};

⛰️ 162 · Find Peak Element ⏱️ O(log n) · 📦 O(1)

💡 ✓ = "the next value is smaller" (going downhill). Find the first ✓. Compare with mid + 1: round-down mid is always < high, so it exists.

// ⛰️ FIND PEAK ELEMENT (walk uphill)
function findPeakElement(nums: number[]): number {
    let low = 0;
    let high = nums.length - 1; // a peak always exists, so no extra slot

    while(low < high) {
        const mid = (low + high) >> 1; // mid < high, so nums[mid + 1] exists

        if(nums[mid] > nums[mid + 1]) high = mid; // going down → a peak is at mid or left
        else low = mid + 1;                        // going up → a peak is to the right
    }

    return low;
};

🔄 4 · Rotated sorted array

"A rotated array is two sorted runs. Compare with the last value to know which run you're in."

🔄 153 · Find Minimum in Rotated Sorted Array ⏱️ O(log n) · 📦 O(1)

💡 First index with nums[i] ≤ nums[n − 1]. Compare with the last value, not the first: an unrotated array would fool nums[0].

// 🔄 FIND MINIMUM IN ROTATED SORTED ARRAY (LEFT: first value <= the last value)
function findMin(nums: number[]): number {
    const n = nums.length;
    let low = 0;
    let high = n - 1; // the minimum always exists

    while(low < high) {
        const mid = (low + high) >> 1;

        if(nums[mid] <= nums[n - 1]) high = mid; // in the low run → min is mid or left
        else low = mid + 1;                       // in the high run → min is to the right
    }

    return nums[low];
};

🔄 33 · Search in Rotated Sorted Array ⏱️ O(log n) · 📦 O(1)

💡 Around mid, one half is always sorted. If the target is inside that sorted half, go there; otherwise go to the other half.

// 🔄 SEARCH IN ROTATED SORTED ARRAY (exact match + "which half is sorted?")
function search(nums: number[], target: number): number {
    let low = 0;
    let high = nums.length - 1;

    while(low <= high) {
        const mid = (low + high) >> 1;

        if(nums[mid] === target) return mid;

        if(nums[low] <= nums[mid]) { // left half is sorted
            if(nums[low] <= target && target < nums[mid]) high = mid - 1;
            else low = mid + 1;
        } else { // right half is sorted
            if(nums[mid] < target && target <= nums[high]) low = mid + 1;
            else high = mid - 1;
        }
    }

    return -1;
};

🎚️ 5 · Binary search on the answer

"Don't search the array. Guess the answer, check it in O(n), keep the half that can still win."

🎚️ 875 · Koko Eating Bananas (first that works) ⏱️ O(n log max) · 📦 O(1)

💡 Hours at speed k = Σ ceil(pile / k). Range 1 … max(pile); the max always works, so no extra slot.

// 🎚️ KOKO EATING BANANAS (LEFT on the answer: slowest speed that works)
function minEatingSpeed(piles: number[], h: number): number {
    function canFinish(speed: number): boolean {
        let hours = 0;
        for(const p of piles) hours += Math.ceil(p / speed);
        return hours <= h;
    }

    let low = 1;
    let high = Math.max(...piles); // the biggest pile per hour always works, so no extra slot

    while(low < high) {
        const mid = (low + high) >> 1;

        if(canFinish(mid)) high = mid; // works → try slower
        else low = mid + 1;
    }

    return low;
};

🎚️ 1011 · Capacity To Ship Packages Within D Days ⏱️ O(n log Σw) · 📦 O(1)

💡 Same shape as 875. Pick low and high as the smallest and largest answers that could ever be right: low = max(weights), high = sum(weights).

// 🎚️ CAPACITY TO SHIP PACKAGES WITHIN D DAYS (same shape as 875)
function shipWithinDays(weights: number[], days: number): number {
    function canShip(cap: number): boolean {
        let need = 1;
        let load = 0;
        for(const w of weights) {
            if(load + w > cap) { // doesn't fit → start a new day
                need++;
                load = 0;
            }
            load += w;
        }
        return need <= days;
    }

    let low = Math.max(...weights);                // must fit the heaviest package
    let high = weights.reduce((a, b) => a + b, 0); // one day ships everything

    while(low < high) {
        const mid = (low + high) >> 1;

        if(canShip(mid)) high = mid;
        else low = mid + 1;
    }

    return low;
};

📏 1552 · Magnetic Force Between Two Balls (last that works) ⏱️ O(n log n + n log range) · 📦 O(1)

💡 "Maximize the minimum gap" → last gap that still fits m balls. RIGHT search, round up.

// 📏 MAGNETIC FORCE BETWEEN TWO BALLS (RIGHT on the answer: biggest gap that works)
function maxDistance(position: number[], m: number): number {
    position.sort((a, b) => a - b);
    const n = position.length;

    function canPlace(gap: number): boolean {
        let balls = 1;
        let last = position[0];
        for(let i = 1; i < n; i++) {
            if(position[i] - last >= gap) {
                balls++;
                last = position[i];
            }
        }
        return balls >= m;
    }

    let low = 1; // positions are distinct, so gap 1 always works
    let high = position[n - 1] - position[0];

    while(low < high) {
        const mid = (low + high + 1) >> 1; // round UP

        if(canPlace(mid)) low = mid; // works → try a bigger gap
        else high = mid - 1;
    }

    return low;
};

🧮 6 · 2D matrix

"Fully sorted → flatten it. Rows and columns sorted → staircase from the top-right."

🧮 74 · Search a 2D Matrix ⏱️ O(log(m·n)) · 📦 O(1)

💡 Exact search on 0 … m·n − 1, with row = floor(mid / n), col = mid % n (n = number of columns).

// 🧮 SEARCH A 2D MATRIX (one sorted list, read row by row)
function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;
    let low = 0;
    let high = m * n - 1;

    while(low <= high) {
        const mid = (low + high) >> 1;
        const val = matrix[Math.floor(mid / n)][mid % n]; // index → (row, col)

        if(val === target) return true;
        else if(val < target) low = mid + 1;
        else high = mid - 1;
    }

    return false;
};

🧮 240 · Search a 2D Matrix II ⏱️ O(m + n) · 📦 O(1)

💡 Start top-right. Too big → move left (that column is out). Too small → move down (that row is out).

// 🧮 SEARCH A 2D MATRIX II (staircase from the top-right, O(m + n))
function searchMatrix(matrix: number[][], target: number): boolean {
    let row = 0;
    let col = matrix[0].length - 1;

    while(row < matrix.length && col >= 0) {
        if(matrix[row][col] === target) return true;
        else if(matrix[row][col] > target) col--; // too big → this whole column is out
        else row++;                                // too small → this whole row is out
    }

    return false;
};

✂️ 7 · Stretch: partition search

"Binary search where to cut the shorter array; the cut in the other array follows."

✂️ 4 · Median of Two Sorted Arrays ⏱️ O(log min(m, n)) · 📦 O(1)

💡 Use ±Infinity for an empty side of a cut. l1 > r2 → took too many from nums1.

// ✂️ MEDIAN OF TWO SORTED ARRAYS (binary search the cut in the shorter array)
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

    const m = nums1.length;
    const n = nums2.length;
    const half = (m + n + 1) >> 1; // size of the left side

    let low = 0;
    let high = m; // take 0..m values from nums1

    while(low <= high) {
        const i = (low + high) >> 1; // values taken from nums1
        const j = half - i;          // the rest come from nums2

        const l1 = i === 0 ? -Infinity : nums1[i - 1];
        const r1 = i === m ? Infinity : nums1[i];
        const l2 = j === 0 ? -Infinity : nums2[j - 1];
        const r2 = j === n ? Infinity : nums2[j];

        if(l1 <= r2 && l2 <= r1) { // every left value <= every right value
            if((m + n) % 2) return Math.max(l1, l2);
            return (Math.max(l1, l2) + Math.min(r1, r2)) / 2;
        }

        if(l1 > r2) high = i - 1; // took too many from nums1
        else low = i + 1;         // took too few
    }

    return -1;
};

⭐ 8 · Must-know, one line each

If you can say the trick for each in one sentence, you're ready.

⚠️ 9 · Traps, and the input that shows each one

Complexity

Why log: each step halves the range, and 2³⁰ ≈ 10⁹, so even a range of a billion takes about 30 steps.

✅ 10 · Self-check

Cover the right column (it's blurred; hover or tap to reveal). Say the answer out loud first.

Write these cold (no peeking)

• 🔍 Exact 704
• 🚧 Boundary 35, 34, 162
• 🔄 Rotated 153, 33
• 🎚️ On the answer 875, 1011, 1552
• 🧮 2D 74

The code on this page is written in your Style A (BS #1) and tested on the LeetCode examples plus random inputs checked against brute force. It isn't your own LeetCode code yet; it gets swapped for yours as you solve each problem.