19.1 binary search แบบวนลูป

หน้า 9.4 เขียน binary search ด้วย recursion เพื่อหาว่าเลขที่ต้องการอยู่ช่องไหน โจทย์ค่าย 2 ถามละเอียดกว่านั้น เช่น มีกี่คนที่ได้คะแนนน้อยกว่า 60 หรือคนแรกที่ได้อย่างน้อย 52 คะแนนอยู่ลำดับที่เท่าไร คำถามแบบนี้ต้องตอบถูกทั้งตอนที่มีค่าซ้ำ และตอนที่ค่าที่ถามไม่มีอยู่ในข้อมูลเลย หน้านี้เปลี่ยน binary search เป็นลูป แล้วเขียนตามกฎข้อเดียวที่ทำให้ทุกขอบถูกโดยไม่ต้องเดา

จาก recursion เป็นลูป

binary search ในหน้า 9.4 เรียกตัวเองแค่ครั้งเดียวต่อชั้น สิ่งที่เปลี่ยนระหว่างชั้นมีแค่ low กับ high จึงเปลี่ยนเป็นลูปได้ตรงๆ แทนที่จะเรียกตัวเองด้วยช่วงใหม่ ก็แก้ค่า low หรือ high แล้ววนกลับไปทำซ้ำ

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

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> ids(n);
    for (int i = 0; i < n; i++) {
        cin >> ids[i];
    }
    int low = 0, high = n - 1;
    int position = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        cout << "low=" << low << " high=" << high << " mid=" << mid << " a[mid]=" << ids[mid] << '\n';
        if (ids[mid] == target) {
            position = mid;
            break;
        }
        if (ids[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << "position = " << position << '\n';
    return 0;
}

10 1460
1012 1047 1105 1188 1230 1302 1377 1419 1460 1525

low=0 high=9 mid=4 a[mid]=1230
low=5 high=9 mid=7 a[mid]=1419
low=8 high=9 mid=8 a[mid]=1460
position = 8

ช่วงที่พิมพ์ออกมาตรงกับหน้า 9.4 ทุกบรรทัด แบบลูปไม่ต้องส่งอาเรย์เป็นพารามิเตอร์ ไม่ใช้ call stack และเพิ่มเงื่อนไขได้ง่ายกว่า ตั้งแต่หน้านี้ไปจะใช้แบบลูปทั้งหมด

เมื่อมีค่าซ้ำ

คะแนนสอบของนักเรียน 8 คนเรียงแล้วเป็น 45 52 52 52 60 71 71 88 ป้อนให้โปรแกรมเดิมหา 52

8 52
45 52 52 52 60 71 71 88

low=0 high=7 mid=3 a[mid]=52
position = 3

เจอ 52 ที่ช่อง 3 ถูกต้องว่ามีอยู่ แต่ถ้าคำถามคือ "มีกี่คนที่ได้น้อยกว่า 52" คำตอบคือ 1 ซึ่งเป็นตำแหน่งของ 52 ตัวแรก ไม่ใช่ตัวที่บังเอิญเจอก่อน วิธีนี้หยุดทันทีที่เจอตัวไหนก็ได้ จึงตอบคำถามแบบนี้ไม่ได้ และถ้าถามหา 55 ซึ่งไม่มีใครได้ ก็ตอบได้แค่ -1 ทั้งที่อยากรู้ว่ามีกี่คนที่ได้น้อยกว่า 55

ช่องแรกที่มีค่าอย่างน้อย x

เปลี่ยนคำถามให้มีคำตอบเสมอ คือ ช่องแรกที่ a[i] >= x อยู่ช่องไหน ถ้าไม่มีเลยให้ตอบ n ลองเขียนผลของเงื่อนไข a[i] >= 52 ไว้ใต้แต่ละช่อง

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

ใช้ตัวแปร lo กับ hi แล้วรักษาสัญญาข้อเดียวไว้ตลอดลูป

สัญญาของ lo กับ hi

ทุกช่อง ก่อน lo ตอบ "ไม่" ทุกช่อง ตั้งแต่ hi เป็นต้นไปตอบ "ใช่" รอยต่อจึงอยู่ระหว่าง lo ถึง hi เสมอ

เริ่มที่ lo = 0 กับ hi = n สัญญาเป็นจริงทันที เพราะยังไม่มีช่องไหนอยู่ก่อนช่อง 0 และไม่มีช่องไหนอยู่ตั้งแต่ช่อง n แต่ละรอบดูช่อง mid ตรงกลาง

ถ้า a[mid] >= x ช่อง mid และทุกช่องทางขวาตอบ "ใช่" ย้าย hi = mid ห้ามเป็น mid - 1 เพราะ mid อาจเป็นช่อง "ใช่" ช่องแรกพอดี
ถ้าไม่ ช่อง mid และทุกช่องทางซ้ายตอบ "ไม่" ย้าย lo = mid + 1

วนจน lo เท่ากับ hi ที่ที่รอยต่ออยู่ได้เหลือจุดเดียว นั่นคือคำตอบ

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

int main()
{
    int n, x;
    cin >> n >> x;
    vector<int> scores(n);
    for (int i = 0; i < n; i++) {
        cin >> scores[i];
    }
    int lo = 0, hi = n; // (1)!
    while (lo < hi) { // (2)!
        int mid = lo + (hi - lo) / 2; // (3)!
        cout << "lo=" << lo << " hi=" << hi << " mid=" << mid << " a[mid]=" << scores[mid] << '\n';
        if (scores[mid] >= x) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << "first index with score >= " << x << " is " << lo << '\n';
    return 0;
}

hi เริ่มที่ n ไม่ใช่ n - 1 เพื่อให้ตอบ n ได้เมื่อไม่มีช่องไหนถึง x ช่อง n ไม่มีอยู่จริง แต่ไม่เคยถูกอ่าน เพราะ mid น้อยกว่า hi เสมอ
ช่วงที่รอยต่ออยู่ได้คือ lo ถึง hi วนจนเหลือจุดเดียว ไม่ใช่ <= แบบโปรแกรมก่อนหน้า
ได้ค่าเดียวกับ (lo + hi) / 2 แต่ไม่ล้นเมื่อ lo กับ hi ใหญ่ ดูในส่วนลองทำให้พัง

8 52
45 52 52 52 60 71 71 88

lo=0 hi=8 mid=4 a[mid]=60
lo=0 hi=4 mid=2 a[mid]=52
lo=0 hi=2 mid=1 a[mid]=52
lo=0 hi=1 mid=0 a[mid]=45
first index with score >= 52 is 1

ช่อง 4 คือ 60 ถึง 52 แล้ว จึงเก็บไว้เป็น hi ช่อง 2 กับช่อง 1 เป็น 52 ก็ถึงเหมือนกัน hi จึงเลื่อนซ้ายต่อ แม้เจอ 52 แล้วก็ยังไม่หยุด เพราะอาจมี 52 ที่อยู่ซ้ายกว่านั้น สุดท้ายช่อง 0 คือ 45 ไม่ถึง lo จึงกลายเป็น 1 เท่ากับ hi แล้วจบ ลองป้อน x อื่นกับคะแนนชุดเดิม

x	คำตอบ	ความหมาย
52	1	52 ตัวแรกอยู่ช่อง 1 มี 1 คนที่ได้น้อยกว่า 52
53	4	ไม่มีใครได้ 53 ถ้าจะแทรก 53 ให้ยังเรียงอยู่ ต้องแทรกที่ช่อง 4
45	0	ตัวแรกสุดก็ถึงแล้ว
10	0	ทุกคนถึง
88	7	มีแค่ช่องสุดท้ายที่ถึง
100	8	ไม่มีใครถึงเลย ได้ n

ทำไมลูปจบแน่นอน

ตอนที่ lo < hi ค่า mid อยู่ระหว่าง lo ถึง hi - 1 เสมอ เพราะการหารปัดเศษลง ทั้ง hi = mid และ lo = mid + 1 จึงทำให้ช่วงสั้นลงอย่างน้อยหนึ่งทุกรอบ และจริงๆ แล้วสั้นลงราวครึ่งหนึ่ง ข้อมูล n ตัววนราว log₂ n รอบ แสนตัวไม่เกิน 17 รอบ ล้านตัวไม่เกิน 20 รอบ ค้นหนึ่งครั้งจึงเป็น O(log n) เทียบกับไล่ทีละช่องที่เป็น O(n)

นับด้วยรอยต่อ

ช่องแรกที่ถึง x บอกจำนวนช่องที่ น้อยกว่า x ไปในตัว เพราะทุกช่องก่อนหน้ามันตอบ "ไม่" ทั้งหมด ถ้าเปลี่ยนเงื่อนไขเป็น a[mid] > x จะได้ช่องแรกที่ มากกว่า x ซึ่งก็คือจำนวนช่องที่ไม่เกิน x สองค่านี้ลบกันได้จำนวนช่องที่เท่ากับ x พอดี

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

int first_at_least(const vector<int> &a, int x) // (1)!
{
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= x) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int first_greater(const vector<int> &a, int x)
{
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > x) { // (2)!
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> scores(n);
    for (int i = 0; i < n; i++) {
        cin >> scores[i];
    }
    for (int k = 0; k < q; k++) {
        int x;
        cin >> x;
        int less = first_at_least(scores, x);
        int at_most = first_greater(scores, x);
        cout << "x=" << x << " less=" << less << " at_most=" << at_most << " equal=" << at_most - less << '\n';
    }
    return 0;
}

ส่ง vector แบบ reference ตามหน้า 16.2 จะได้ไม่ต้องคัดลอกข้อมูลแสนตัวทุกครั้งที่เรียก const บอกว่าฟังก์ชันนี้จะไม่แก้ข้อมูล ถ้าเผลอแก้ compiler จะฟ้อง
ต่างจากฟังก์ชันแรกแค่ >= กับ > ตัวเดียว

8 5
45 52 52 52 60 71 71 88
52
53
71
10
100

x=52 less=1 at_most=4 equal=3
x=53 less=4 at_most=4 equal=0
x=71 less=5 at_most=7 equal=2
x=10 less=0 at_most=0 equal=0
x=100 less=8 at_most=8 equal=0

คำถามอื่นที่เจอบ่อยก็ได้จากสองฟังก์ชันนี้ เช่น ช่องสุดท้ายที่ไม่เกิน x คือ first_greater(a, x) - 1 ถ้าได้ -1 แปลว่าไม่มีช่องไหนเลย และจำนวนคนที่ได้อย่างน้อย x คือ n - first_at_least(a, x) ก่อนเขียน ให้ถามตัวเองว่าคำถามคือ "รอยต่อของเงื่อนไขอะไร" แล้วค่อยเลือกว่าใช้ >= หรือ >

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

วัดบนโน้ตบุ๊ก AMD Ryzen AI 9 HX 370 กับ Windows 11 และ GCC 14.2 ของ Code::Blocks คะแนน N = 100000 ตัว สุ่มตั้งแต่ 1 ถึง 10⁹ แล้วเรียงไว้ มีคำถาม Q = 100000 ข้อ แต่ละข้อถามว่ามีกี่ตัวที่น้อยกว่า x วิธีตรงไปตรงมาไล่จากช่องซ้ายสุดจนเจอตัวที่ถึง x ซึ่งเฉลี่ยต้องไล่ครึ่งอาเรย์ทุกคำถาม เป็น O(NQ) ส่วน binary search เป็น O(Q log N) รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลางของ 5 รอบ

วิธี	Code::Blocks (`-Wall`)	`-O2`
ไล่จากซ้าย	10.1 วินาที (5 รอบอยู่ระหว่าง 8.4 ถึง 11.3)	2.0 วินาที
binary search	0.06 วินาที	0.06 วินาที

วิธีไล่ต้องเทียบราว 5 × 10⁹ ครั้ง ส่วน binary search เทียบไม่เกิน 17 × 10⁵ ครั้ง เวลาที่เหลือ 0.06 วินาทีเกือบทั้งหมดคือการอ่านตัวเลขสองแสนตัว แม้ -O2 จะช่วยวิธีไล่ได้ห้าเท่า ก็ยังเกิน 1 วินาทีอยู่ดี

ลองทำให้พัง

แบบที่ 1 เขียน lo = mid

ในโปรแกรม first-at-least เปลี่ยน lo = mid + 1; เป็น lo = mid; เพราะคิดว่าดูช่อง mid ซ้ำอีกรอบก็ไม่เสียหาย แล้วป้อน 8 100 กับคะแนนชุดเดิม

lo=0 hi=8 mid=4 a[mid]=60
lo=4 hi=8 mid=6 a[mid]=71
lo=6 hi=8 mid=7 a[mid]=88
lo=7 hi=8 mid=7 a[mid]=88
lo=7 hi=8 mid=7 a[mid]=88
lo=7 hi=8 mid=7 a[mid]=88
lo=7 hi=8 mid=7 a[mid]=88
lo=7 hi=8 mid=7 a[mid]=88

พิมพ์บรรทัดเดิมไม่หยุดจนต้องปิดหน้าต่างเอง พอช่วงเหลือ lo=7 hi=8 ค่า mid ปัดลงได้ 7 ช่อง 7 คือ 88 ไม่ถึง 100 จึงตั้ง lo = 7 ซึ่งเป็นค่าเดิม ช่วงไม่สั้นลงเลย ถ้าลบบรรทัดที่พิมพ์ออก โปรแกรมจะค้างเงียบๆ และ grader ให้ผลว่าเกินเวลา ทั้งที่ทุกบรรทัดดูถูก ลองหา 52 ซึ่งมีอยู่จริงก็ค้างเหมือนกัน คราวนี้ค้างที่ lo=0 hi=1 mid=0

เป็นกฎเดียวกับหน้า 9.4 ทุกรอบช่วงต้องสั้นลง ฝั่งที่ตอบ "ไม่" ตัด mid ทิ้งไปด้วย ฝั่งที่ตอบ "ใช่" เก็บ mid ไว้ ทดสอบ binary search ทุกครั้งด้วย x ที่น้อยกว่าทุกตัว มากกว่าทุกตัว เท่ากับตัวแรก เท่ากับตัวสุดท้าย และค่าที่ซ้ำ

แบบที่ 2 mid ล้น

ในหน้านี้ hi ไม่เกิน n จึงไม่มีปัญหา แต่หน้า 19.3 จะค้นบนช่วงของคำตอบที่ใหญ่ถึงพันล้าน ถ้าหาจุดกลางด้วย (lo + hi) / 2 แบบ int

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

int main()
{
    int lo, hi;
    cin >> lo >> hi;
    cout << (lo + hi) / 2 << '\n';
    cout << lo + (hi - lo) / 2 << '\n';
    return 0;
}

1500000000 2000000000

-397483648
1750000000

lo + hi คือ 3.5 × 10⁹ เกิน int ล้นเป็นค่าติดลบตามหน้า 1.3 จุดกลางจึงติดลบ ถ้าเอาไปใช้เป็น index ก็อ่านนอกอาเรย์ ถ้าใช้เป็นคำตอบก็ผิด ส่วน lo + (hi - lo) / 2 ไม่ล้น เพราะ hi - lo ไม่เกิน hi และบวกกลับแค่ครึ่งเดียว อีกทางคือประกาศ lo hi mid เป็น long long ไปเลย ซึ่งหน้า 19.3 จะทำแบบนั้นเมื่อช่วงใหญ่

สรุป

เปลี่ยนคำถามเป็น "รอยต่อของเงื่อนไข" ที่เป็น "ไม่" ทางซ้ายและ "ใช่" ทางขวา แล้วหาช่อง "ใช่" ช่องแรก
เริ่ม lo = 0 กับ hi = n วน while (lo < hi) ถ้า "ใช่" ให้ hi = mid ถ้า "ไม่" ให้ lo = mid + 1 จบแล้วคำตอบคือ lo
ช่องแรกที่ >= x คือจำนวนที่น้อยกว่า x ช่องแรกที่ > x คือจำนวนที่ไม่เกิน x สองค่าลบกันได้จำนวนที่เท่ากับ x
ค้นหนึ่งครั้งเป็น O(log n) แสนตัวไม่เกิน 17 รอบ
ทุกรอบช่วงต้องสั้นลง lo = mid ทำให้ลูปไม่จบ
หาจุดกลางด้วย lo + (hi - lo) / 2 หรือใช้ long long เมื่อช่วงใหญ่