Làm thế nào để giải quyết bài toán tìm kiếm căn bậc hai nguyên (Integer Square Root) sử dụng giải thuật Binary Search và tránh các lỗi về hiệu năng cũng như kiểu dữ liệu?

Question

Accepted Answer

Bản chất cơ chế hoạt động Bài toán yêu cầu tìm căn bậc hai nguyên của một số không âm x, lấy phần nguyên (ví dụ: sqrt(8) = 2). Thay vì dùng hàm toán học thông thường, ta có thể áp dụng Binary Search trong khoảng từ 0 đến x: Đặt left = 0, right = x. Tính mid = left + (right - left) // 2. So sánh mid * mid với x. Nếu mid * mid <= x, ta lưu mid làm kết quả tạm thời và thử tìm giá trị lớn hơn ở bên phải (left = mid + 1). Ngược lại, nếu mid * mid > x, ta tìm ở bên trái (right = mid - 1). Độ phức tạp thời gian là O(log x). Ví dụ triển khai bằng mã nguồn (Python) def my_sqrt(x): if x < 2: return x left, right = 2, x // 2 result = -1 while left <= right: mid = left + (right - left) // 2 sqr = mid * mid if sqr == x: return mid elif sqr < x: result = mid left = mid + 1 else: right = mid - 1 return result Khi nào nên sử dụng? Ứng dụng trong các bài toán tối ưu hóa phân bổ tài nguyên, tính toán không gian bộ nhớ, hoặc các thuật toán đồ họa cần ước lượng khoảng cách nhanh mà không dùng dấu phẩy động (floating-point). Kinh nghiệm thực chiến cho Junior Tránh tràn số (Integer Overflow): Trong các ngôn ngữ như Java, C++, phép tính mid * mid với số nguyên lớn có thể gây tràn bộ nhớ. Nên dùng kiểu dữ liệu lớn hơn hoặc chuyển đổi phép so sánh thành mid <= x // mid. Tối ưu phạm vi tìm kiếm: Căn bậc hai của một số x (với x >= 2) không bao giờ vượt quá x // 2, do đó việc khởi tạo right = x // 2 giúp giảm số bước lặp đáng kể.

Làm thế nào để giải quyết bài toán tìm kiếm căn bậc hai nguyên (Integer Square Root) sử dụng giải thuật Binary Search và tránh các lỗi về hiệu năng cũng như kiểu dữ liệu?

Bản chất cơ chế hoạt động

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi searching liên quan cùng chủ đề