19.4 binary search บนจำนวนจริง

บางโจทย์คำตอบเป็นทศนิยม เช่น ระดับน้ำ เวลาที่ใช้ ความเร็ว ค่าเหล่านี้ไม่มีคำว่า "ค่าถัดไป" แบบจำนวนเต็ม ช่วงที่ค้นจึงไม่มีวันหดจนเหลือค่าเดียวพอดี หน้านี้ใช้ความคิดเดิมจากหน้า 19.3 กับคำตอบที่เป็น double แล้วเปลี่ยนวิธีหยุดลูปเป็นวนจำนวนรอบที่กำหนดไว้ ซึ่งปลอดภัยกว่าการรอให้ช่วงแคบลงเอง

ลองกับรากที่สอง

รากที่สองของ x คือค่า m ที่ m × m = x ใช้คำถามใช่ไม่ใช่ว่า m * m >= x ไหม ยิ่ง m มากยิ่งตอบใช่ จึงเป็นทางเดียว คำตอบอยู่ระหว่าง 0 ถึง x ถ้า x ไม่น้อยกว่า 1 แต่ถ้า x น้อยกว่า 1 เช่น 0.25 รากที่สองคือ 0.5 ซึ่งมากกว่า x จึงให้ hi เป็นค่าที่มากกว่าระหว่าง 1 กับ x

ต่างจากจำนวนเต็มสองจุด ไม่มีบวกหนึ่งหรือลบหนึ่ง เพราะไม่มีค่าถัดไปให้ข้าม ตั้ง lo = mid หรือ hi = mid ตรงๆ และไม่ใช้ while (lo < hi) แต่วนให้ครบ 100 รอบ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    double x;
    cin >> x;
    double lo = 0, hi = max(1.0, x);
    for (int step = 0; step < 100; step++) { // (1)!
        double mid = (lo + hi) / 2;
        if (mid * mid >= x) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << fixed << setprecision(9); // (2)!
    cout << "binary search: " << hi << '\n';
    cout << "sqrt:          " << sqrt(x) << '\n';
    return 0;
}

1. วนครบ 100 รอบเสมอ ไม่ว่าช่วงจะแคบแค่ไหนแล้ว เหตุผลอยู่ในหัวข้อถัดไป
2. fixed กับ setprecision(9) คือทศนิยม 9 ตำแหน่ง แบบเดียวกับ printf("%.9f") ในบทที่ 2 ตั้งครั้งเดียวมีผลกับทุกค่าที่พิมพ์ต่อจากนั้น

2

binary search: 1.414213562
sqrt:          1.414213562

ตรงกับ sqrt ทั้ง 9 ตำแหน่ง ลองป้อน x อื่นก็ได้ตรงกัน เช่น 10 ได้ 3.162277660 ทั้งคู่ 0.5 ได้ 0.707106781 ทั้งคู่ และ 123456789 ได้ 11111.111060556 ทั้งคู่ แน่นอนว่าโจทย์จริงไม่ต้องหารากที่สองเอง ตัวอย่างนี้มีไว้ให้เห็นว่าลูปแบบนี้ได้ความละเอียดเท่าที่ double เก็บได้

ทำไมต้อง 100 รอบ

ทุกรอบช่วงแคบลงครึ่งหนึ่ง ถ้าช่วงเริ่มกว้าง 10⁹ ความกว้างหลังวน k รอบคือ 10⁹ หารด้วย 2^k

double แม่นราว 15 ถึง 16 หลักตามหน้า 1.4 ค่าใกล้ 10⁹ จึงแม่นได้ถึงราวทศนิยมตำแหน่งที่ 6 หรือ 7 เท่านั้น พอวนไปราว 60 รอบ ช่วงก็แคบจนติดขีดจำกัดของ double แล้ว รอบที่เหลือไม่ได้ทำให้แม่นขึ้น แต่ก็ไม่ทำให้เสียหาย 100 รอบจึงเผื่อไว้สบายๆ สำหรับช่วงกว้างแค่ไหนก็ได้ เวลาทั้งหมดคือ 100 คูณเวลาตรวจหนึ่งครั้ง ถ้าตรวจหนึ่งครั้งเป็น O(N) ที่ N เป็นแสน ก็ราว 10⁷ ขั้น สบายมาก

ระดับน้ำ

แท็งก์น้ำแบ่งเป็น N ช่องเรียงกัน ช่องละกว้าง 1 เมตร ผนังกั้นสูงมาก พื้นของแต่ละช่องสูงไม่เท่ากัน ช่องที่ i สูง h_i เมตร ทุกช่องมีท่อเล็กๆ เชื่อมถึงกันใต้พื้น เทน้ำลงไป V ตารางเมตร (มองเป็นภาพตัดขวางสองมิติ และไม่คิดน้ำที่ค้างในท่อ) น้ำจะไหลถึงกันจนผิวน้ำของทุกช่องที่มีน้ำอยู่ระดับเดียวกัน ถามว่าผิวน้ำอยู่สูงเท่าไร ตอบทศนิยม 4 ตำแหน่ง

ถ้าผิวน้ำอยู่ที่ระดับ L ช่องที่พื้นต่ำกว่า L จะมีน้ำสูง L - h_i ช่องที่พื้นสูงกว่าไม่มีน้ำ น้ำทั้งหมดใต้ระดับ L จึงคำนวณได้ในลูปเดียว คำถามใช่ไม่ใช่คือ "ใต้ระดับ L จุน้ำได้อย่างน้อย V ไหม" ยกระดับขึ้น ทุกช่องจุได้เท่าเดิมหรือมากขึ้น จึงเป็นทางเดียว และคำตอบคือ L ที่น้อยที่สุดที่ตอบใช่

#include <bits/stdc++.h>
using namespace std;

double water_below(const vector<int> &floor_height, double level)
{
    double total = 0;
    for (int i = 0; i < (int)floor_height.size(); i++) {
        if (level > floor_height[i]) {
            total += level - floor_height[i];
        }
    }
    return total;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    double volume;
    cin >> n >> volume;
    vector<int> floor_height(n);
    int highest = 0;
    for (int i = 0; i < n; i++) {
        cin >> floor_height[i];
        highest = max(highest, floor_height[i]);
    }
    double lo = 0, hi = highest + volume; // (1)!
    for (int step = 0; step < 100; step++) {
        double mid = (lo + hi) / 2;
        if (water_below(floor_height, mid) >= volume) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << fixed << setprecision(4) << hi << '\n';
    return 0;
}

1. ที่ระดับ highest + volume ช่องไหนก็ตามมีน้ำสูงอย่างน้อย volume แล้ว จึงตอบใช่แน่นอน ส่วนระดับ 0 ไม่มีน้ำเลย

5 6
3 1 4 1 5

3.6667

ตรวจด้วยมือ ระดับต้องอยู่ระหว่าง 3 ถึง 4 เพราะที่ระดับ 3 จุได้แค่ 0 + 2 + 0 + 2 + 0 = 4 ตารางเมตร ช่วงนี้มีน้ำสามช่องคือช่องที่พื้นสูง 3 1 1 จึงได้ 3L - 5 = 6 ได้ L = 11/3 = 3.6667 ตรงกัน ถ้าจะคิดด้วยสูตรแบบนี้ ต้องรู้ก่อนว่าระดับอยู่ช่วงไหน ซึ่งต้องเรียงความสูงแล้วไล่หา ส่วน binary search ไม่ต้องรู้อะไรเลยนอกจากวิธีคำนวณน้ำใต้ระดับหนึ่งๆ

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาคือไล่ระดับขึ้นทีละ 0.0001 เมตรจาก 0 จนกว่าน้ำใต้ระดับจะถึง V จำนวนรอบเท่ากับคำตอบคูณหนึ่งหมื่น วัดบนเครื่องเดียวกับหน้า 19.1 แท็งก์ N = 1000 ช่อง พื้นสูงสุ่มตั้งแต่ 0 ถึง 100 เมตร เทน้ำ V = 50000 ผิวน้ำอยู่ที่ราว 99 เมตร วิธีไล่จึงต้องตรวจราวหนึ่งล้านครั้ง ครั้งละ 1000 ช่อง รันแต่ละแบบ 5 รอบ

วิธีไล่ไม่ได้แค่ช้า แต่ยังได้คำตอบผิดในตำแหน่งสุดท้าย ค่าจริงคือ 99.015136 กว่าๆ วิธีไล่หยุดที่ขั้นแรกที่น้ำพอ คือ 99.0152 ซึ่งเกินค่าจริงไปแล้ว ถ้าจะให้ปัดถูกต้องไล่ละเอียดกว่านี้อีกสิบเท่า ก็ช้าลงอีกสิบเท่า ส่วน binary search ที่ N = 100000 ช่องและน้ำห้าล้านตารางเมตร ยังใช้แค่ 0.10 วินาทีทั้งสองแบบ

ลองทำให้พัง

แบบที่ 1 หยุดเมื่อช่วงแคบกว่า 10^-9

หลายคนหยุดลูปเมื่อช่วงแคบพอ แทนการวนจำนวนรอบที่กำหนด แบบนี้

while (hi - lo > 1e-9) {
    double mid = (lo + hi) / 2;
    if (water_below(floor_height, mid) >= volume) {
        hi = mid;
    } else {
        lo = mid;
    }
}

ข้อมูลเข้าชุดเดิมได้ 3.6667 ถูกต้อง แต่ลองแท็งก์สามช่องที่พื้นสูงระดับพันล้าน 3 7 กับ 1000000000 999999999 1000000000 โปรแกรมค้าง ใส่บรรทัดพิมพ์ lo กับ hi ทุก 20 รอบด้วย setprecision(17) จะเห็นว่า

step 20 lo=999999053.32567692 hi=1000000007
step 40 lo=1000000001.999598 hi=1000000002.0005076
step 60 lo=1000000001.9999999 hi=1000000002
step 80 lo=1000000001.9999999 hi=1000000002
step 100 lo=1000000001.9999999 hi=1000000002
step 120 lo=1000000001.9999999 hi=1000000002
step 140 lo=1000000001.9999999 hi=1000000002
step 160 lo=1000000001.9999999 hi=1000000002

ตั้งแต่รอบที่ 60 lo กับ hi ไม่ขยับอีกเลย double ที่อยู่ใกล้ 10⁹ เก็บค่าได้ห่างกันทีละราว 1.2 × 10^-7 ไม่มีค่าไหนอยู่ระหว่าง lo กับ hi คู่นี้แล้ว จุดกลางที่คำนวณได้จึงปัดกลับไปเท่ากับ lo หรือ hi เดิม ช่วงไม่มีทางแคบกว่า 10^-9 ได้ ลูปจึงไม่จบ การวนจำนวนรอบที่กำหนดไม่มีปัญหานี้ เพราะไม่ได้รอให้ช่วงแคบ

แบบที่ 2 พิมพ์ double ด้วย cout เฉยๆ

ในโปรแกรม water-level ลบ fixed << setprecision(4) << ออก เหลือ cout << hi << '\n';

#include <bits/stdc++.h>
using namespace std;

double water_below(const vector<int> &floor_height, double level)
{
    double total = 0;
    for (int i = 0; i < (int)floor_height.size(); i++) {
        if (level > floor_height[i]) {
            total += level - floor_height[i];
        }
    }
    return total;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    double volume;
    cin >> n >> volume;
    vector<int> floor_height(n);
    int highest = 0;
    for (int i = 0; i < n; i++) {
        cin >> floor_height[i];
        highest = max(highest, floor_height[i]);
    }
    double lo = 0, hi = highest + volume;
    for (int step = 0; step < 100; step++) {
        double mid = (lo + hi) / 2;
        if (water_below(floor_height, mid) >= volume) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << hi << '\n';
    return 0;
}

3 7
1000000000 999999999 1000000000

1e+09

คำตอบที่ถูกคือ 1000000002.0000 แต่ cout ที่ไม่ได้ตั้งค่าอะไร พิมพ์ทศนิยมแค่ 6 หลักสำคัญ ค่าที่ใหญ่จึงกลายเป็นรูปวิทยาศาสตร์ 1e+09 ส่วนข้อมูลเข้าชุดแรกพิมพ์ออกมาเป็น 3.66667 ซึ่งก็ผิดรูปแบบที่โจทย์ต้องการอยู่ดี โจทย์ที่ตอบเป็นทศนิยมต้องใส่ fixed กับ setprecision ทุกครั้ง หรือใช้ printf("%.4f\n", hi)

สรุป

• คำตอบเป็นทศนิยมก็ใช้ binary search ได้ ถ้าคำถามใช่ไม่ใช่เป็นทางเดียว
• ตั้ง lo = mid หรือ hi = mid ไม่มีบวกลบหนึ่ง และวนจำนวนรอบที่กำหนด เช่น 100 รอบ
• อย่าหยุดด้วย hi - lo > eps เพราะเมื่อค่าใหญ่ double แคบได้ไม่ถึง eps ลูปจะไม่จบ
• เวลาทั้งหมดคือ 100 คูณเวลาตรวจหนึ่งครั้ง
• พิมพ์คำตอบด้วย fixed กับ setprecision หรือ printf ตามจำนวนตำแหน่งที่โจทย์กำหนด