EasyModified Binary Search

Sqrt(x)

Explanation & Solution

Description

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 (e.g., Math.sqrt or **).

Input: x = 4

Output: 2

Explanation: The square root of 4 is 2.

Constraints

0 <= x <= 2^31 - 1

Approach

Modified Binary Search pattern

1. Handle Base Cases

If x < 2, return x directly (sqrt(0) = 0, sqrt(1) = 1).

2. Binary Search on [1, x]

Set lo = 1, hi = x, and track ans.
Compute mid and check if mid <= x / mid (using division instead of mid * mid to avoid overflow).

3. Update Answer

If mid <= x / mid, then mid could be the answer → save it, search higher: lo = mid + 1.
Otherwise, mid is too large: hi = mid - 1.

4. Return

ans holds the largest integer whose square is ≤ x.

🧠 Key Insight

Using mid <= x / mid instead of mid * mid <= x prevents integer overflow for large values of x.

Time

O(log x)binary search over [1, x].

Space

O(1).

Solution Code

Capacity To Ship Packages Within D Days

Single Element in a Sorted Array