Binary Search – DSA Notes

Classic monotonic/partition-based binary searches.

---

📌 Summary Table

Problem	Monotonic / Partition Idea	Binary Search On	Time	Space
N-th Root of M	Power grows with base	Base x in [1..m]	O(n · log m)	O(1)
Median in Row-wise Sorted Matrix	Count ≤ mid increases with mid	Value mid in [min..max]	O(r · log c · log V)	O(1)
Single Element in Sorted Array	Pair alignment flips after single	Index	O(log n)	O(1)
Search in Rotated Sorted Array	One half is always sorted	Index	O(log n)	O(1)
Median of Two Sorted Arrays	Correct partition satisfies LA ≤ RB & LB ≤ RA	Cut position	O(log(min(n,m)))	O(1)
K-th Element of Two Sorted Arrays	Partition with cutA + cutB = k	CutA	O(log(min(n,m)))	O(1)
Book Allocation	Feasibility non-decreasing with max pages	Answer (max pages)	O(n · log ΣA)	O(1)
Aggressive Cows / Magnetic Force	Placability increases with distance	Distance	O(n · log Range)	O(1)

Notation: r,c = rows & cols; V = value range; ΣA = sum of pages; Range = max(position) - min(position).

---

N-th Root of M

Problem. Find an integer x such that x^n = m. If no integer root exists, return -1.

Idea. Binary search base x in [1, m]. For each mid, compute mid^n with early stop if it exceeds m to avoid overflow.

Complexity. O(n · log m) (power per step), O(1) space.

class Solution {
    // Compute a^n with early stopping once it exceeds 'limit'
    private long pow(long a, int n, long limit) {
        long r = 1;
        for (int i = 0; i < n; i++) {
            r *= a;
            if (r > limit) return limit + 1; // sentinel: "too big"
        }
        return r;
    }

    public int NthRoot(int n, int m) {
        int lo = 1, hi = m;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long p = pow(mid, n, m);
            if (p == m) return mid;        // exact integer root
            if (p < m) lo = mid + 1;       // need bigger base
            else hi = mid - 1;             // too big
        }
        return -1; // no integer root
    }
}

Key Takeaway. Search base; use early-stop power to tame overflow.

---

Median in Row-wise Sorted Matrix

Problem. Each row is sorted. Find the matrix median.

Idea. Binary search on value mid between global min and max. For each mid, count how many elements ≤ mid by doing an upper-bound in every row.

Complexity. O(r · log c · log V).

class Solution {
    // Count of elements <= x in a sorted row (upper bound index)
    int countLE(int[] row, int x) {
        int lo = 0, hi = row.length - 1, ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (row[mid] <= x) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans + 1;
    }

    int median(int[][] mat, int r, int c) {
        int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
        // value range across rows
        for (int i = 0; i < r; i++) {
            lo = Math.min(lo, mat[i][0]);
            hi = Math.max(hi, mat[i][c - 1]);
        }

        int desired = (r * c + 1) / 2; // 1-based index of median
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int cnt = 0;
            for (int i = 0; i < r; i++) cnt += countLE(mat[i], mid);
            if (cnt < desired) lo = mid + 1; // need larger values
            else hi = mid;                    // enough elements <= mid
        }
        return lo;
    }
}

Key Takeaway. Search value space; check count ≤ mid.

---

Single Element in Sorted Array (every other appears twice)

Problem. Sorted array where every element appears exactly twice except one. Return that single.

Idea. Before the single, pairs start at even indices; after it, they start at odd. Use mid ^ 1 to pair with neighbor (mid^1 flips last bit: pairs 0↔1, 2↔3, …).

Complexity. O(log n).

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.length - 2; // avoid out-of-bounds on mid^1
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == nums[mid ^ 1]) {
                lo = mid + 1;   // single is to the right
            } else {
                hi = mid - 1;   // single is at mid or to the left
            }
        }
        return nums[lo];
    }
}

Key Takeaway. Pair-index trick with mid ^ 1.

---

Search in Rotated Sorted Array

Problem. Find target in a rotated sorted array (distinct values).

Idea. At each step, one half is sorted. Decide which half to keep by checking if target lies inside the sorted half.

Complexity. O(log n).

class Solution {
    public int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] == target) return mid;

            if (a[lo] <= a[mid]) { // left half sorted
                if (a[lo] <= target && target < a[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {               // right half sorted
                if (a[mid] < target && target <= a[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

Key Takeaway. Sorted half test narrows the search.

---

Median of Two Sorted Arrays (Partition)

Problem. Return median of two sorted arrays.

Idea. Binary search the cut in the smaller array so that: LA ≤ RB and LB ≤ RA. Then median is middle of max left & min right depending on parity.

Complexity. O(log(min(n, m))).

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        if (A.length > B.length) return findMedianSortedArrays(B, A);
        int n = A.length, m = B.length, lo = 0, hi = n;

        while (lo <= hi) {
            int cutA = (lo + hi) >>> 1;
            int cutB = (n + m + 1) / 2 - cutA;

            int LA = (cutA == 0) ? Integer.MIN_VALUE : A[cutA - 1];
            int LB = (cutB == 0) ? Integer.MIN_VALUE : B[cutB - 1];
            int RA = (cutA == n) ? Integer.MAX_VALUE : A[cutA];
            int RB = (cutB == m) ? Integer.MAX_VALUE : B[cutB];

            if (LA <= RB && LB <= RA) {
                if (((n + m) & 1) == 0)
                    return (Math.max(LA, LB) + Math.min(RA, RB)) / 2.0;
                else
                    return Math.max(LA, LB);
            } else if (LA > RB) {
                hi = cutA - 1; // move cutA left
            } else {
                lo = cutA + 1; // move cutA right
            }
        }
        return 0.0; // unreachable for valid inputs
    }
}

Key Takeaway. Partition condition: LA ≤ RB and LB ≤ RA.

---

K-th Element of Two Sorted Arrays

Problem. Return the k-th smallest (1-indexed) from two sorted arrays.

Idea. Binary search cutA where cutA + cutB = k. Check the same partition inequalities.

Complexity. O(log(min(n, m))).

class Solution {
    public long kthElement(int[] A, int[] B, int n, int m, int k) {
        if (n > m) return kthElement(B, A, m, n, k); // ensure A is smaller
        int lo = Math.max(0, k - m), hi = Math.min(k, n);

        while (lo <= hi) {
            int cutA = (lo + hi) >>> 1;
            int cutB = k - cutA;

            int LA = (cutA == 0) ? Integer.MIN_VALUE : A[cutA - 1];
            int LB = (cutB == 0) ? Integer.MIN_VALUE : B[cutB - 1];
            int RA = (cutA == n) ? Integer.MAX_VALUE : A[cutA];
            int RB = (cutB == m) ? Integer.MAX_VALUE : B[cutB];

            if (LA <= RB && LB <= RA) {
                return Math.max(LA, LB);
            } else if (LA > RB) {
                hi = cutA - 1;
            } else {
                lo = cutA + 1;
            }
        }
        return -1; // invalid k
    }
}

Key Takeaway. Same partition trick as median, but stop at k.

---

Book Allocation (Minimize Max Pages)

Problem. Split books (array A) into M contiguous parts to minimize the maximum pages assigned to any student. If M > N, return -1.

Idea. Binary search the answer maxPages. The feasibility predicate: can we allocate with ≤ maxPages per student using at most M students?

Complexity. O(n · log ΣA).

class Solution {
    // Check if we can allocate with 'maxPages' as the per-student cap
    private static boolean can(int[] A, int students, int maxPages) {
        int need = 1, sum = 0;
        for (int x : A) {
            if (x > maxPages) return false;     // single book too large
            if (sum + x > maxPages) {           // new student
                need++;
                sum = x;
            } else {
                sum += x;
            }
        }
        return need <= students;
    }

    public static int findPages(int[] A, int N, int M) {
        if (M > N) return -1;
        int lo = 0, hi = 0;
        for (int x : A) { hi += x; lo = Math.max(lo, x); } // lo=max book, hi=sum

        int ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1; // candidate max pages
            if (can(A, M, mid)) { ans = mid; hi = mid - 1; } // try smaller
            else lo = mid + 1;                                // need larger
        }
        return ans;
    }
}

Key Takeaway. Feasibility over answer space (classic parametric search).

---

Aggressive Cows / Magnetic Force

Problem. Place m cows in stalls (position[]) to maximize the minimum distance between any two cows.

Idea. Binary search distance d. Predicate canPlace(d): greedily place next cow at the earliest stall ≥ last + d.

Complexity. O(n · log Range) after sorting.

class Solution {
    // Can we place 'm' cows with at least 'dist' apart?
    private boolean canPlace(int[] pos, int m, int dist) {
        int cnt = 1, last = pos[0];  // place first cow at first stall
        for (int i = 1; i < pos.length; i++) {
            if (pos[i] - last >= dist) {
                cnt++;
                last = pos[i];
                if (cnt >= m) return true; // all cows placed
            }
        }
        return cnt >= m;
    }

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int lo = 1, hi = position[position.length - 1] - position[0], ans = 0;

        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (canPlace(position, m, mid)) { ans = mid; lo = mid + 1; } // try bigger d
            else hi = mid - 1;                                           // too large d
        }
        return ans;
    }
}

Key Takeaway. Greedy placement forms a monotone predicate over distance.

---