69. Sqrt(x)
Tags:
Easy
Skills:
Math
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm căn bậc hai nguyên của một số nguyên không âm x, tức la tìm số nguyên lớn nhất y sao cho y^2 ≤ x. Không được dùng các hàm căn bậc hai và phép lũy thừa có sẵn
Approach - Binary search
mid * mid so với để thu hẹp khoảng cách tìm kiếm. Khi kết thúc, return về giá trị lớn nhất sao cho bình phương không vượt quá x. Cách này tối ưu với độ phức tạp O(logx)Giải thích chi tiết về binary search
Time and space complexity
Solution
1function mySqrt(x: number): number {
2 if(x < 2) return x;
3 let left = 1, right = x;
4 while(left <= right) {
5 const mid = left + Math.floor((right - left) / 2);
6 const square = mid * mid;
7 if(square === x) return mid
8 else if (square < x) left = mid + 1
9 else right = mid - 1
10 }
11 return right
12};