DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Binary Search Patterns

The Two Categories of Binary Search

Most developers know binary search for finding a target in a sorted array. Interview problems, however, use binary search in two very different ways:

Category 1: Search in a Sorted Array
  Input:  a sorted array, a target value
  Output: an index (or -1)
  Key:    arr[mid] compared to target decides which half to search

Category 2: Search on the Answer Space
  Input:  a problem with a numeric answer in range [lo, hi]
  Output: the minimum/maximum answer satisfying a condition
  Key:    condition(mid) tells whether mid is a valid answer
          The condition is monotonic: all values below threshold fail,
          all values above pass (or the reverse)

  The "array" being searched is the range of possible answers,
  not the actual input array.

Pattern recognition: if the problem says "find the minimum X such that…" or "find the maximum X such that…" and X is a number with a clear range — binary search on the answer space.

The Universal Binary Search Template

All binary search variants reduce to one template. The only difference is what condition(mid) checks.

Template — find the LEFTMOST position where condition transitions from false to true:

  lo = minimum possible answer
  hi = maximum possible answer

  while lo < hi:
      mid = lo + (hi - lo) / 2

      if condition(mid):
          hi = mid          ← mid could be the answer — keep it in range
      else:
          lo = mid + 1      ← mid fails — discard it

  return lo   ← first position where condition is true

Invariant:
  Everything left of lo  → condition is false
  Everything right of hi → condition is true
  Answer: lo when loop ends (lo == hi)

To find the RIGHTMOST position where condition is false:
  if condition(mid): hi = mid - 1
  else:             lo = mid
  return lo (or hi)  after loop

The standard binary search (find target) is a special case:

condition(mid) = arr[mid] >= target
→ finds leftmost index where arr[mid] >= target
→ if arr[lo] == target: found; else: not present

Pattern 1: Find Peak Element

Problem: A peak element is greater than its neighbours. Find the index of any peak element. An element at the boundary only needs to be greater than its one neighbour.

Binary search insight: If arr[mid] < arr[mid+1], the peak must be to the right — because the sequence is still rising at mid. If arr[mid] > arr[mid+1], the peak must be to the left (or at mid) — the sequence is falling. Binary search narrows to the peak.

Java

public class FindPeakElement {

    // Find any peak element — O(log n)
    public static int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length - 1;

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            if (nums[mid] < nums[mid + 1]) {
                // Rising slope — peak is to the RIGHT
                lo = mid + 1;
            } else {
                // Falling or equal — peak is HERE or to the LEFT
                hi = mid;
            }
        }

        return lo;   // lo == hi — the peak index
    }

    // Find a LOCAL peak in a 2D grid — extend to row/column
    public static int[] findPeakGrid(int[][] mat) {
        int lo = 0, hi = mat[0].length - 1;

        while (lo <= hi) {
            int midCol = lo + (hi - lo) / 2;
            int maxRow = 0;

            // Find the row with maximum value in midCol
            for (int r = 0; r < mat.length; r++) {
                if (mat[r][midCol] > mat[maxRow][midCol]) maxRow = r;
            }

            boolean leftBigger  = midCol > 0 && mat[maxRow][midCol - 1] > mat[maxRow][midCol];
            boolean rightBigger = midCol < mat[0].length - 1 && mat[maxRow][midCol + 1] > mat[maxRow][midCol];

            if      (!leftBigger && !rightBigger) return new int[]{maxRow, midCol};
            else if (leftBigger)                  hi = midCol - 1;
            else                                  lo = midCol + 1;
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        System.out.println(findPeakElement(new int[]{1, 2, 3, 1}));      // 2
        System.out.println(findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4})); // 5
        System.out.println(findPeakElement(new int[]{1}));                // 0
        System.out.println(findPeakElement(new int[]{5, 4, 3, 2, 1}));   // 0 — decreasing
        System.out.println(findPeakElement(new int[]{1, 2, 3, 4, 5}));   // 4 — increasing
    }
}

Output:
2
5
0
0
4

Dry Run: `[1, 2, 1, 3, 5, 6, 4]`

lo=0, hi=6

Iter 1: mid=3, nums[3]=3, nums[4]=5. 3 < 5 → rising → lo=4
Iter 2: lo=4, hi=6, mid=5, nums[5]=6, nums[6]=4. 6 > 4 → falling → hi=5
Iter 3: lo=4, hi=5, mid=4, nums[4]=5, nums[5]=6. 5 < 6 → rising → lo=5

lo=5 == hi=5 → return 5

nums[5]=6 > nums[4]=5 AND nums[5]=6 > nums[6]=4 ✓ — confirmed peak

Pattern 2: Search on Answer Space — Koko Eating Bananas

Problem: Koko has piles of bananas and h hours. She eats at speed k bananas per hour — one pile per hour, eating min(pile, k) per hour. Find the minimum k so she finishes in h hours.

Binary search insight: The minimum valid speed is 1. The maximum needed is max(piles) — eating the largest pile in one hour always works. For a given speed k, compute total hours needed and check if it fits within h. This check is monotonic — if speed k works, any speed > k also works. Binary search on [1, max(piles)].

Java

public class KokoEatingBananas {

    // Check if speed k is fast enough to finish all piles in h hours
    private static boolean canFinish(int[] piles, int h, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + k - 1) / k;   // ceil(pile / k)
        }
        return hours <= h;
    }

    public static int minEatingSpeed(int[] piles, int h) {
        int lo = 1;
        int hi = 0;
        for (int p : piles) hi = Math.max(hi, p);   // max(piles)

        // Find minimum k where canFinish is true
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            if (canFinish(piles, h, mid)) {
                hi = mid;        // mid works — try smaller
            } else {
                lo = mid + 1;    // mid doesn't work — need faster
            }
        }

        return lo;   // Minimum valid speed
    }

    public static void main(String[] args) {
        System.out.println(minEatingSpeed(new int[]{3, 6, 7, 11}, 8));    // 4
        System.out.println(minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 5)); // 30
        System.out.println(minEatingSpeed(new int[]{30, 11, 23, 4, 20}, 6)); // 23
    }
}

Output:
4
30
23

Dry Run: `piles=[3,6,7,11], h=8`

lo=1, hi=11

Iter 1: mid=6
  hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)
        = 1 + 1 + 2 + 2 = 6 ≤ 8 → canFinish=true → hi=6

Iter 2: lo=1, hi=6, mid=3
  hours = ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3)
        = 1 + 2 + 3 + 4 = 10 > 8 → canFinish=false → lo=4

Iter 3: lo=4, hi=6, mid=5
  hours = ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5)
        = 1 + 2 + 2 + 3 = 8 ≤ 8 → canFinish=true → hi=5

Iter 4: lo=4, hi=5, mid=4
  hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4)
        = 1 + 2 + 2 + 3 = 8 ≤ 8 → canFinish=true → hi=4

lo=4 == hi=4 → return 4 ✓

Monotonic check:
  k=3: 10 hours > 8 → FAIL
  k=4:  8 hours ≤ 8 → PASS ← minimum
  k=5:  8 hours ≤ 8 → PASS
  k=6:  6 hours ≤ 8 → PASS
All values from 4 onwards pass — binary search finds the transition.

Pattern 3: Minimum Capacity to Ship Packages in D Days

Problem: Packages with weights must all be shipped within D days. Ship in order — one shipment per day, capacity C per day. Find minimum C.

Same pattern as Koko: Binary search on [max(weights), sum(weights)]. For a given capacity C, simulate shipping and count days needed.

Java

public class ShipPackages {

    private static boolean canShip(int[] weights, int D, int capacity) {
        int days = 1, load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;        // Start a new day
                load = 0;
            }
            load += w;
        }
        return days <= D;
    }

    public static int shipWithinDays(int[] weights, int D) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = Math.max(lo, w);    // Must carry heaviest package
            hi += w;                 // Can carry everything in one day
        }

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, D, mid)) hi = mid;
            else                          lo = mid + 1;
        }

        return lo;
    }

    public static void main(String[] args) {
        System.out.println(shipWithinDays(new int[]{1,2,3,4,5,6,7,8,9,10}, 5)); // 15
        System.out.println(shipWithinDays(new int[]{3,2,2,4,1,4}, 3));           // 6
        System.out.println(shipWithinDays(new int[]{1,2,3,1,1}, 4));             // 3
    }
}

Output:
15
6
3

Pattern 4: Aggressive Cows — Maximum Minimum Distance

Problem: Place C cows in N stalls (given positions). Maximise the minimum distance between any two cows.

Binary search insight: Binary search on the minimum distance d in [1, max(stalls) - min(stalls)]. For a given d, greedily check if C cows can be placed such that every pair is at least d apart.

Java

import java.util.Arrays;

public class AggressiveCows {

    private static boolean canPlace(int[] stalls, int cows, int minDist) {
        int count = 1, last = stalls[0];

        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - last >= minDist) {
                count++;
                last = stalls[i];
                if (count == cows) return true;
            }
        }
        return count >= cows;
    }

    public static int maxMinDistance(int[] stalls, int cows) {
        Arrays.sort(stalls);

        int lo = 1;
        int hi = stalls[stalls.length - 1] - stalls[0];
        int result = 0;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (canPlace(stalls, cows, mid)) {
                result = mid;    // mid distance is achievable — try larger
                lo = mid + 1;
            } else {
                hi = mid - 1;   // mid distance too large — try smaller
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(maxMinDistance(new int[]{1,2,4,8,9}, 3)); // 3
        System.out.println(maxMinDistance(new int[]{1,2,3,4,5}, 2)); // 4
    }
}

Output:
3
4

Pattern 5: Median of Two Sorted Arrays

Problem: Find the median of two sorted arrays combined in O(log(min(m,n))).

Binary search insight: Binary search on the partition point in the smaller array. A correct partition means maxLeft1 ≤ minRight2 and maxLeft2 ≤ minRight1. Adjust the partition until valid.

Java

public class MedianSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Always binary search on the smaller array
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

        int m = nums1.length, n = nums2.length;
        int lo = 0, hi = m;

        while (lo <= hi) {
            int partX = lo + (hi - lo) / 2;    // Partition in nums1
            int partY = (m + n + 1) / 2 - partX;  // Partition in nums2

            int maxLeftX  = partX == 0 ? Integer.MIN_VALUE : nums1[partX - 1];
            int minRightX = partX == m ? Integer.MAX_VALUE : nums1[partX];

            int maxLeftY  = partY == 0 ? Integer.MIN_VALUE : nums2[partY - 1];
            int minRightY = partY == n ? Integer.MAX_VALUE : nums2[partY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                // Correct partition found
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
                } else {
                    return Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                hi = partX - 1;    // Move partition left in nums1
            } else {
                lo = partX + 1;    // Move partition right in nums1
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1,3}, new int[]{2}));         // 2.0
        System.out.println(findMedianSortedArrays(new int[]{1,2}, new int[]{3,4}));       // 2.5
        System.out.println(findMedianSortedArrays(new int[]{}, new int[]{1}));            // 1.0
        System.out.println(findMedianSortedArrays(new int[]{1,3,5}, new int[]{2,4,6}));   // 3.5
    }
}

Output:
2.0
2.5
1.0
3.5

Pattern 6: Nth Root of a Number

Problem: Find the Nth root of M (integer Nth root — largest integer x such that xᴺ ≤ M).

Java

public class NthRoot {

    private static long power(long base, int exp) {
        long result = 1;
        for (int i = 0; i < exp; i++) {
            result *= base;
            if (result > 1_000_000_000L) return result;  // Early overflow exit
        }
        return result;
    }

    public static int nthRoot(int n, int m) {
        int lo = 1, hi = m;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long pw  = power(mid, n);

            if (pw == m) return mid;
            else if (pw < m) lo = mid + 1;
            else             hi = mid - 1;
        }

        return -1;   // m is not a perfect nth power
    }

    public static void main(String[] args) {
        System.out.println(nthRoot(3, 27));   // 3  (3³ = 27)
        System.out.println(nthRoot(2, 25));   // 5  (5² = 25)
        System.out.println(nthRoot(4, 81));   // 3  (3⁴ = 81)
        System.out.println(nthRoot(3, 26));   // -1 (not a perfect cube)
    }
}

Output:
3
5
3
-1

Answer-Space Pattern Recognition Guide

The key question: is there a monotonic function from the answer space to true/false?

Problem                           | lo          | hi            | condition(mid)
──────────────────────────────────────────────────────────────────────────────────
Koko eating bananas               | 1           | max(piles)    | hours ≤ h
Ship packages in D days           | max(weights)| sum(weights)  | days ≤ D
Aggressive cows (max min dist)    | 1           | max-min stalls| can place cows
Allocate minimum pages            | max(pages)  | sum(pages)    | students ≤ k
Split array largest sum           | max(arr)    | sum(arr)      | parts ≤ m
Book allocation                   | max(books)  | sum(books)    | allocate ≤ m students
Capacity to ship (reverse)        | max(w)      | sum(w)        | days ≤ D
Minimum days to make bouquets     | 1           | max(day)      | bouquets ≥ m
Smallest divisor ≤ threshold      | 1           | max(arr)      | sum(ceil/d) ≤ threshold
Square root (integer)             | 1           | n/2           | mid² ≤ n

Template:
  All "find minimum X such that condition holds" → lo seeks upward until condition passes
  All "find maximum X such that condition holds" → result updated when condition passes, lo moves up

Common Mistakes in Patterns

Using lo < hi vs lo <= hi — the wrong termination condition for the problem.

›Use lo < hi for the universal template (answer space) where hi = mid keeps mid in range
›Use lo <= hi for standard index search where hi = mid - 1 excludes mid
›Mixing them causes infinite loops or off-by-one errors

Not identifying the monotonic boundary. Every answer-space binary search depends on a monotonic condition. Before coding, verify: "All values below the answer fail the condition. All values from the answer upward pass." If the condition is not monotonic — binary search cannot be applied.

Setting lo and hi incorrectly in answer-space search. lo must be the smallest possible valid answer (never too small to exclude the real answer). hi must be the largest needed (never too large to cause overflow in the condition check). For shipping: lo = max(weights) because the capacity must hold the heaviest item; lo = 0 would mean capacity can be 0 — invalid.

Off-by-one in ceiling division. ceil(a / b) in integer arithmetic is (a + b - 1) / b. Using a / b (floor) gives the wrong number of hours/days — the canFinish check then returns incorrect results for non-divisible values.

Peak element: using nums[mid] <= nums[mid+1] (with equals). Equal adjacent elements mean both halves could contain a peak. The strict < comparison is standard for the problem variant that guarantees no equal adjacent elements. Check problem constraints before adding =.

Interview Questions

Q: How do you recognise that a problem requires binary search on the answer space?

Four signals: (1) the problem asks for a minimum or maximum value, (2) there is a clear numeric range for the answer, (3) there is a feasibility check that can be computed in O(n) or O(n log n), and (4) the feasibility is monotonic — if speed k works, speed k+1 also works (or vice versa). When you see "find the minimum X such that we can achieve Y," write the canAchieve(X) function first, then wrap it in binary search.

Q: Why is the universal template lo < hi instead of lo <= hi?

The lo < hi template is used when hi = mid (inclusive upper bound update). With lo < hi, the loop exits when lo == hi — one element remains, which is the answer. If lo <= hi were used with hi = mid, the loop would not terminate when lo == hi because mid = lo and hi = mid = lo would not reduce the range. The lo <= hi template pairs with hi = mid - 1 (exclusive update) — both correctly terminate.

Q: In the median of two sorted arrays, why binary search on the smaller array?

The partition in the larger array (partY) is fully determined by partX — it is (m+n+1)/2 - partX. So only one partition index needs to be searched. Binary searching on the smaller array (length m) gives O(log m) which is O(log(min(m,n))). If we always ensured m ≤ n by swapping, partY is always valid (never negative or out of range), avoiding boundary checks.

FAQs

Can binary search on the answer space handle non-integer answers?

Yes — use floating-point binary search. Instead of lo < hi, run a fixed number of iterations (typically 100) since floating-point ranges never reduce to exactly equal: for i in range(100): mid = (lo+hi)/2; if condition(mid): hi=mid else: lo=mid. Used for problems like finding the minimum speed in continuous time or the exact nth root of a real number.

Is binary search on answer space always O(n log(range))?

Yes, where range = hi - lo is the answer space size and n is the cost of the condition check. Each binary search iteration costs O(condition) and there are O(log(range)) iterations. For Koko: O(n log(max_pile)) where n = number of piles. For shipping: O(n log(sum)) where n = number of weights.

How does aggressive cows differ from Koko — both seem to use the same template?

Both binary search on a value range with a feasibility check. The difference: Koko minimises speed (answer increases toward valid), so canFinish → hi = mid. Aggressive cows maximises minimum distance (answer is the largest valid), so canPlace → result = mid; lo = mid + 1 (keep searching right for a larger valid value). The feasibility check direction determines whether you take hi = mid (minimum valid) or lo = mid + 1; result = mid (maximum valid).

Summary

Binary search patterns fall into two categories: array search (covered in the previous topic) and answer-space search (this page).

Pattern 1 — Peak Element:

›lo < hi template; nums[mid] < nums[mid+1] → lo = mid+1; else hi = mid
›Terminates at a peak without checking all elements

Pattern 2 — Answer Space (Minimum Valid):

›lo = min_answer, hi = max_answer; while lo < hi
›if condition(mid): hi = mid else lo = mid + 1
›Returns lo — the first value where condition is true
›Problems: Koko, ship packages, allocate pages, smallest divisor

Pattern 3 — Answer Space (Maximum Valid):

›Same setup; if condition(mid): result = mid; lo = mid + 1 else hi = mid - 1
›Returns result — the last value where condition is true
›Problems: Aggressive cows, maximum allocation size

Pattern 4 — Partition Search:

›Binary search on one partition index; derive the other
›Both partitions correct when cross-condition holds
›Problem: Median of two sorted arrays — O(log(min(m,n)))

Recognition signal summary:

›"Find minimum X such that…" → hi = mid template
›"Find maximum X such that…" → result = mid; lo = mid + 1 template
›"Find peak / any valid answer" → lo < hi with slope direction
›"Combine two sorted structures" → partition binary search

In the next topic, you will explore Lower Bound and Upper Bound — the precise boundary-finding operations that underlie first/last occurrence, count of elements in range, and insertion point problems.

Suggested Quiz

Binary search on the answer space is applicable when?

1/6

←

PreviousBinary Search

NextPractice Problems

→