หารากที่สองของจำนวนถึงความแม่นยำที่กำหนดด้วย Binary Search ใน C++

โจทย์

ให้จำนวน N และความแม่นยำ P (จำนวนทศนิยม) ต้องการหารากที่สองของ N ถึง P ตำแหน่งทศนิยม ใช้ Binary Search

ตัวอย่าง: N=50, P=3 → 7.071

วิธีแก้ปัญหา

1. ส่วนจำนวนเต็ม: Binary Search หาค่า mid ที่ mid² ≤ N < (mid+1)²
2. ส่วนทศนิยม: เริ่ม increment = 0.1 ลูป P รอบ:
   • while (res² ≤ N) res += increment
   • res -= increment (ย้อนกลับ 1 ขั้น)
   • increment /= 10

ตัวอย่างโค้ด C++

#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;
}

ผลลัพธ์

Square root of 50 up to precision 3 is: 7.071