CMD Guide
Home › DSA

Searching

Step 16 in the DSA path · 2 concepts · 6 problems

0 / 8 complete

📘 Learn Searching from zero

The Searching pattern means reframing a problem as binary search: keep a candidate range, probe its midpoint, and discard the half that provably cannot contain the answer — halving the space each step for O(log N). The classic trigger is a sorted array, but the real FAANG unlock is binary search on the answer: when the answer lives in a numeric range and a predicate is monotonic (true before some threshold, false after it), you binary-search the value space itself. Canonical example: mySqrt(x) — find floor(sqrt(17)). The "array" is the conceptual range [1..17], and the monotone predicate is mid*mid <= x.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Frame the search space
x = 17,  find largest m with m*m <= 17

candidate value space (conceptual, sorted):
  1  2  3  4  5  6  7  8  9 10 11 ... 17
  ^                                    ^
  lo                                  hi

predicate P(m) = (m*m <= 17):
  m:  1  2  3  4  5  6  7  ...  17
  P:  T  T  T  T  F  F  F  ...   F   <- monotone: once false, stays false

There is no real array — we binary-search the answer range lo=1, hi=17. The predicate m*m <= 17 is monotone (a True block then a False block), so a threshold exists and binary search is valid. We want the last True, so we track ans whenever the predicate holds.

Step 2 — Probe mid = 9
lo=1                              hi=17
  1  2  3  4  5  6  7  8 [9]10 ... 17
  ^                      ^          ^
  lo                    mid        hi

mid = 1 + (17-1)/2 = 9
mid*mid = 81  >  17   -> predicate FALSE

mid = lo + (hi-lo)/2 = 9, and 9*9 = 81 > 17. Since the predicate is monotone, every value >= 9 also fails, so the entire right half (9..17) is safe to discard. We move hi = mid - 1 = 8. State: lo=1, hi=8, ans=-1.

Step 3 — Probe mid = 4
lo=1         hi=8
  1  2  3 [4] 5  6  7  8
  ^        ^           ^
  lo      mid         hi

mid = 1 + (8-1)/2 = 4
mid*mid = 16  <=  17  -> predicate TRUE
ans = 4  (record this candidate)

mid = 1 + (8-1)/2 = 4, and 4*4 = 16 <= 17, so 4 is a valid answer. Because we seek the largest valid value, we record ans = 4 and search higher: lo = mid + 1 = 5. Everything <= 4 is now known-good and discarded. State: lo=5, hi=8, ans=4.

Step 4 — Probe mid = 6
      lo=5     hi=8
  5  [6] 7  8
  ^   ^      ^
  lo mid    hi

mid = 5 + (8-5)/2 = 6
mid*mid = 36  >  17  -> predicate FALSE

mid = 5 + (8-5)/2 = 6, and 6*6 = 36 > 17. The right half (6..8) all fails by monotonicity, so we discard it: hi = mid - 1 = 5. State: lo=5, hi=5, ans=4 — the window has shrunk to a single value.

Step 5 — Probe mid = 5
  lo=5
  hi=5
 [5]
  ^
  lo=mid=hi

mid = 5 + (5-5)/2 = 5
mid*mid = 25  >  17  -> predicate FALSE

The window is one element: mid = 5, and 5*5 = 25 > 17, predicate FALSE. We discard it with hi = mid - 1 = 4. Now lo = 5 > hi = 4, so the loop will terminate — the range is empty and no candidate is left to test. State: lo=5, hi=4, ans=4.

Step 6 — Terminate and return ans
lo=5 > hi=4   -> loop ends (empty range)

final predicate picture:
  m :  1  2  3  4 | 5  6  7 ... 17
  P :  T  T  T  T | F  F  F ...  F
                  ^
        threshold between last-True (4) and first-False (5)

return ans = 4        (floor(sqrt(17)) = 4, since 4^2=16<=17<25=5^2)

The loop exits exactly when lo > hi; ans holds the last value that satisfied the predicate, which is the floor of sqrt we wanted: 4. We probed only 4 values (9, 4, 6, 5) instead of 17 — that is the O(log N) win.

Step 7 — Generalize the pattern
BINARY SEARCH ON ANSWER (template)

 lo = min feasible, hi = max feasible
 ans = -1
 while lo <= hi:
     mid = lo + (hi - lo) / 2     # avoids overflow
     if P(mid):      ans = mid; lo = mid + 1   # want largest True
     else:           hi = mid - 1
 return ans

Map to the in-scope problems:
  Sqrt(x)                         P(m): m*m <= x
  Freq of Most Frequent Element   P(len): window costs <= k ops
  Minimize Max of Two Arrays      P(v): v has enough multiples
  Search a 2D Matrix II           staircase from top-right corner

Whenever the answer is a number in a range and a yes/no test on a guess is monotone, binary-search the value space. Use mid = lo + (hi-lo)/2 to dodge integer overflow, and decide the lo=mid+1 vs hi=mid-1 update by whether you want the last-True or first-True boundary.

🎯 Guided practice

  1. Easy — Maximum Count of Positive and Negative Integers. Given a sorted array (e.g. [-3,-1,0,0,2,4,5]), return max(count of negatives, count of positives). Brute force is an O(n) scan, but "sorted" is the trigger for O(log n). Step 1: negatives form a contiguous prefix, positives a contiguous suffix, zeros sit between — a monotonic structure. Step 2: binary-search the first index where value ≥ 0; since every negative is strictly before it, that index equals the count of negatives (here, index 2 → 2 negatives). Step 3: binary-search the first index where value ≥ 1 (the first strictly-positive element, index 4); positives = n - that index = 7 - 4 = 3. Step 4: return max(2, 3) = 3. Core pattern learned: "first index satisfying a monotonic condition" (the lower-bound template) converts counting into two O(log n) boundary searches.
  2. Medium — Frequency of the Most Frequent Element. Given nums and budget k (allowed total increments), maximize the count of one equal value. Step 1 (recognize): increments only go up, and it's cheapest to raise smaller numbers up to a target — so sort the array first: [1,2,4], k=5. Step 2 (window invariant): for a window [l..r], the cheapest equalization makes everything equal to the largest, nums[r]. Cost = nums[r]*(r-l+1) - sum(window). Step 3 (slide): expand r one step, add to a running window sum; while cost exceeds k, shrink from l. Track the max window size. Walk it on sorted [1,2,4]: window [1] cost 0 (size 1); window [1,2] cost 2*2-3=1 ≤ 5 (size 2); window [1,2,4] cost 4*3-7=5 ≤ 5 (size 3). Answer: 3. Why it's a searching pattern: the cost is monotonically non-decreasing as the window grows for a fixed right end, so the two-pointer sweep is O(n) after the O(n log n) sort — far better than O(n²) checking every pair. (Binary-searching the leftmost valid l for each r also works; two pointers is the tighter version of the same monotonic idea.)

✨ Added by the guide — work these before the full problem set.

Lessons in this topic

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
What is the trigger signal for linear search vs binary search, and what prerequisite does binary search impose?
tap to reveal →
Linear search scans every element sequentially and works on any array regardless of order, so it suits small or unsorted data; binary search requires a sorted array because it discards half the remaining elements per comparison. Linear search is O(n); binary search is O(log n).
💡 Sorted? Bisect. Unsorted/tiny? Scan.
Flashcard
In the binary-search-on-the-answer template, how do you decide between lo=mid+1 and hi=mid-1, and why use mid = lo + (hi-lo)/2?
tap to reveal →
When the predicate P(mid) holds you record ans=mid and move toward the boundary you want (lo=mid+1 for the last-True, hi=mid-1 for the first-True); otherwise move the opposite pointer. Use mid = lo + (hi-lo)/2 to avoid integer overflow from lo+hi.
💡 Record-then-push toward the boundary; (hi-lo)/2 dodges overflow.
Flashcard
How does Maximum Count of Positive and Negative Integers exploit the sorted array, and what is its complexity?
tap to reveal →
Negatives form a contiguous prefix and positives a contiguous suffix, so two binary searches find the boundaries: count negatives (last index where nums[mid]<0) and count positives (nums.length - first positive index), then return the max. Two independent O(log n) searches, O(1) space.
💡 Prefix of negatives, suffix of positives — bisect each boundary.
Flashcard
What is the mySqrt(x) approach, its search range, and why must you cast mid*mid to long?
tap to reveal →
Binary-search the integer y in range left=2 to right=x/2 for the largest y with y*y <= x; handle x<2 by returning x. The predicate mid*mid <= x is monotone; compute num=(long)mid*mid because mid*mid can overflow 32-bit int. Return right after the loop. Time O(log x), space O(1).
💡 Floor of sqrt = last-True of m*m<=x; cast to long or it overflows.
Flashcard
For Frequency of the Most Frequent Element, what preprocessing is needed and how is the cost of equalizing a window computed?
tap to reveal →
Sort the array, then build a cumulative-sum array. For a window [mid..i] targeting nums[i], operations needed = target*(i-mid+1) - (sum of that window via prefix sums). Binary-search the leftmost valid mid per i where ops <= k. Time O(n log n), space O(n).
💡 Sort + prefix sum; cost = target*count - windowSum.
Flashcard
How does Search a 2D Matrix II achieve O(m+n), and why start at the top-right corner?
tap to reveal →
From the top-right element: if it equals target return true; if it's less than target move down (rows increase downward), if greater move left (columns increase rightward). Each comparison eliminates a whole row or column, so it visits at most m+n-1 cells. Time O(m+n), space O(1).
💡 Top-right staircase: bigger? go left; smaller? go down.
Q1. In mySqrt for x=8, the lesson sets left=2, right=x/2=4 and probes mid=3 first (3*3=9>8). What happens and what is finally returned?
Q2. Why does Search a 2D Matrix II start at the top-right corner rather than the top-left?
Q3. For Frequency of the Most Frequent Element with nums=[10,9,9,4,8], k=5, what must be done before the binary search and what is the answer?
Q4. In Maximum Count of Positive and Negative Integers, after finding the boundaries on a sorted array, how are the two counts derived?
Q5. Minimize the Maximum of Two Arrays binary-searches a candidate maximum value mid and checks feasibility using the LCM of the divisors. Why is the LCM needed?