Binary Search
41 / 170Binary SearchLesson 3 of 8About 67 min
The technique that makes binary search apply to problems with no sorted array anywhere in sight.
Integer square root is the smallest useful case. There is no array at all; the candidates are the integers from 0 to n, and the property is that the square reaches n.
def integer_sqrt(n): low, high = 0, n + 1 while low < high: mid = low + (high - low) // 2 if mid * mid >= n: high = mid else: low = mid + 1 return low print(integer_sqrt(17), integer_sqrt(16), integer_sqrt(0))Here the candidate is a capacity, and testing one requires walking the whole input. The total cost is the log of the candidate range times the cost of one test.
def days_needed(loads, capacity): days, current = 1, 0 for load in loads: if current + load > capacity: days += 1 current = 0 current += load return days def smallest_capacity(loads, allowed_days): low, high = max(loads), sum(loads) # both bounds are defensible while low < high: mid = low + (high - low) // 2 if days_needed(loads, mid) <= allowed_days: high = mid else: low = mid + 1 return low print(smallest_capacity([1, 2, 3, 4, 5], 2))Write the three decisions on paper: the candidate range with a justification for each bound, the feasibility test, and why feasibility is monotone. The problem below is straightforward once those exist and genuinely hard without them.
Answer-space searches live or die on the feasibility function, so write two of those and one search. groups_needed returns how many groups are needed if no group may exceed limit, splitting only between adjacent items. smallest_limit finds the smallest limit fitting within allowed groups. smallest_side returns the smallest integer side length whose square is at least area.
Tests
print(groups_needed([1, 2, 3, 4, 5], 5), groups_needed([1, 2, 3, 4, 5], 15))print(smallest_limit([1, 2, 3, 4, 5], 2), smallest_limit([1, 2, 3, 4, 5], 5))print(smallest_side(17), smallest_side(16), smallest_side(0))Output
Run tests to see output.
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.