Sqrt(x)
The key idea
The answer
r is the largest integer whose square does not exceed x. Since r*r grows monotonically with r, you can binary-search the range [0, x] for that boundary instead of scanning every candidate.Problem
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator such as pow(x, 0.5) in C++ or x ** 0.5 in Python.
Constraints
- 0 <= x <= 2^31 - 1
Examples
Input: x = 4
Output: 2
Input: x = 8
Output: 2
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD