Giả sử có số dương n và độ chính xác p. Tìm căn bậc hai của n đến p chữ số thập phân dùng tìm kiếm nhị phân. Nếu n = 50, p = 3, kết quả 7.071.
Giải quyết theo các bước:
- Khởi tạo start := 0 và end := n
- So sánh bình phương mid với số, nếu bằng thì phần nguyên tìm thấy, ngược lại tìm bên trái/phải.
- Sau khi xong phần nguyên, làm phần thập phân.
- Khởi tạo biến tăng 0.1, tính phần thập phân đến p vị trí. Mỗi lần lặp tăng giảm 1/10 lần trước.
- Trả về kết quả.
Ví dụ mã nguồn
#include<iostream> using namespace std; float sqrtBinarySearch(int num, int p) { int left = 0, right = num; int mid; float res; while (left <= right) { mid = (left + right) / 2; if (mid * mid == num) { res = mid; break; } if (mid * mid < num) { left = mid + 1; res = mid; } else { right = mid - 1; } } float incr = 0.1; for (int i = 0; i < p; i++) { while (res * res <= num) { res += incr; } res -= incr; incr /= 10; } return res; } int main() { int n = 50, p = 3; cout << "Square root of " << n << " up to precision " << p << " is: " << sqrtBinarySearch(50, 3) << endl; } Kết quả
Square root of 50 up to precision 3 is: 7.071