Micro-Drill #273 — Integer square root (bisect)

Search Target: 10s

Binary search for the largest integer whose square <= x. Return hi (not lo) because lo overshoots by 1.

lo, hi = 0, x
while lo &lt;= hi:
    mid = (lo + hi) // 2
    if mid * mid &lt;= x:
        lo = mid + 1
    else:
        hi = mid - 1
return hi

Type it from memory. Go.