Fundamental Algorithms8 sections · 291 units
Open in Course

Template - Find Maximum Valid

Template for finding the last value satisfying a condition.

Find max xx where isValid(x) is true (monotonic: once false, stays false).

function findMaxValid(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo + 1) / 2
        if isValid(mid): lo = mid
        else: hi = mid - 1
    return lo

Note: +1 in mid rounds up to avoid infinite loops.

Uses: Max weight in bag, largest square in grid, last good version.