Binary Search
Author: njoop & Pasit Sangprachathanarak
Binary Search คืออะไร
Binary Search หรือการค้นหาแบบทวิภาค เป็นวิธีการค้นหาข้อมูลที่ใช้กับข้อมูลที่มีการเรียงลำดับแล้ว โดยจะนำข้อมูลมาแบ่งครึ่ง และพิจารณาว่าข้อมูลที่ต้องการจะค้นหาอยู่ที่ครึ่งไหน และทำซ้ำๆ ไปเรื่อยๆ
Binary search สามารถทำได้โดยมีขั้นตอนดังนี้
- กำหนดตำแหน่งข้อมูลที่น้อย และมากที่สุดที่เป็นไปได้ (แทนค่าด้วยตัวแปร \(L\), \(R\) ตามลำดับ โดยช่วง \([L, R]\) จะเป็นช่วงที่เป็นไปได้ที่มจะมีข้อมูลที่เราต้องการค้นหาอยู่)
- หาค่าตรงกลาง ระหว่าง \(L\) กับ \(R\) ให้ค่านี้เป็น \(mid\)
- ตรวจสอบข้อมูลในตำแหน่ง \(mid\)
- ถ้าเกิดข้อมูลเป็นสิ่งที่เราค้นหา ก็จบการทำงาน โดยเราพบเจอข้อมูลที่เราค้นหาแล้ว
- ถ้าเกิดข้อมูลน้อยกว่าสิ่งที่เราค้นหา ให้ค่า \(L = mid+1\) (เพราะไม่มีทางที่ข้อมูลที่เราต้องการ อยู่ระหว่าง \(L\) และ \(mid\) แน่นอน)
- ถ้าเกิดข้อมูลมากกว่าสิ่งที่เราค้นหา ให้ค่า \(R = mid-1\) (เพราะไม่มีทางที่ข้อมูลที่เราต้องการ อยู่ระหว่าง \(mid\) และ \(R\) แน่นอน)
- ทำซ้ำไปเรื่อยๆ จนกว่า \(L > R\) (แสดงว่าไม่มีข้อมูลที่ค้นหาอยู่) หรือพบข้อมูลที่ต้องการ
หมายเหตุ
- สามารถหาค่า \(mid\) ได้หลายวิธี โดยปกติมักทำโดยการนำค่า \(\frac{L+R}{2}\) ปัดเศษลง แต่ก็สามารถปัดเศษขึ้นได้เหมือนกัน
- การกำหนดค่า \(L\) และ \(R\) ใหม่ ก็สามารถทำได้หลายวิธี เช่น ถ้าเกิดมีข้อมูลซ้ำ และเราต้องการหาข้อมูลที่ตรงและมีตำแหน่งมากที่สุด อาจเปลี่ยนจาก \(R = mid-1\) เป็น \(R = mid\) แทน
Binary search ในชีวิตประจำวัน
เราอาจใช้ Binary search ในชีวิตประจำวันโดยไม่รู้ตัว ตัวอย่างการใช้งานเช่น:
มีหนังสือ 8 เล่ม โดยที่ชื่อหนังสือแต่ละเล่มนั้น เรียงลำดับตามพจนานุกรม ตามตาราง
| หนังสือเล่มที่ | ชื่อหนังสือ |
|---|---|
| 1 | Ascendance of a bookworm |
| 2 | Harry potter |
| 3 | Jobless Reincarnation |
| 4 | Lycoris Recoil |
| 5 | Omniscient Reader's Viewpoint |
| 6 | Reverend Insanity |
| 7 | Secrets of the Silent Witch |
| 8 | The Beginning After The End |
ถ้าเกิดต้องการหาว่า "Omniscient Reader's Viewpoint" เป็นหนังสือเล่มที่เท่าไหร่ จะมีวิธีหลักๆ อยู่ 2 วิธี คือ
วิธีที่ 1 (Sequential search หรือ Linear search)
- ตรวจสอบหนังสือเล่มที่ 1 สังเกตว่าหนังสือเล่มนั้นไม่ใช่ "Omniscient Reader's Viewpoint" จึงไปดูหนังสือเล่มต่อไป
- ตรวจสอบหนังสือเล่มที่ 2 สังเกตว่าหนังสือเล่มนั้นไม่ใช่ "Omniscient Reader's Viewpoint" จึงไปดูหนังสือเล่มต่อไป
- ทำซ้ำไปเรื่อยๆ จนเจอ "Omniscient Reader's Viewpoint" หรือดูหนังสือครบทุกเล่ม
วิธีที่ 2 (Binary search)
- สังเกตว่า มีหนังสือ 8 เล่ม
- ตรวจสอบหนังสือเล่มที่ 4 หรือ 5 เนื่องจากทั้งตำแหน่งกึ่งกลางอาจเป็น 4 หรือ 5 ก็ได้ ในที่นี้เราเลือกหนังสือเล่มที่ 4 สังเกตว่า "Lycoris recoil" มาก่อน "Omniscient Reader's Viewpoint" ตามลำดับพจนานุกรม ดังนั้น หนังสือเล่มที่ 1 ถึง 4 ไม่มีทางเป็น "Omniscient Reader's Viewpoint" แน่นอน หนังสือที่เป็นไปได้จึงเป็นหนังสือเล่มที่ 5 ถึง 8
- ตรวจสอบหนังสือเล่มที่ 6 หรือ 7 ในที่นี้เราเลือกหนังสือเล่มที่ 7 สังเกตว่า "Secrets of the Silent Witch" มาหลัง "Omniscient Reader's Viewpoint" ตามลำดับพจนานุกรม ดังนั้น หนังสือที่เป็นไปได้จึงเป็นหนังสือเล่มที่ 5 ถึง 6
- ตรวจสอบหนังสือเล่มที่ 5 ซึ่งมีชื่อ "Omniscient Reader's Viewpoint" ตามที่เราต้องการ จึงสามารถสรุปได้ว่า "Omniscient Reader's Viewpoint" เป็นหนังสือเล่มที่ 5
Binary search vs Sequential search
สังเกตว่า วิธีที่ 1 จำเป็นต้องตรวจสอบหนังสืออย่างมาก 8 เล่ม แต่วิธีที่ 2 จำเป็นต้องตรวจสอบหนังสือแค่ 3 เล่ม ซึ่งดูเหมือนจะไม่ได้เร็วขึ้นกว่ากันมาก แต่ถ้าเกิดมีหนังสือ 1 ล้านเล่ม วิธีที่ 2 จะตรวจสอบหนังสือแค่ 20 เล่มเท่านั้น
ถ้าเกิดมีหนังสือ n เล่ม
- วิธีที่ 1 (sequential search) ตรวจสอบอย่างมาก n ครั้ง หรือ \(O(n)\)
- วิธีที่ 2 (binary search) ตรวจสอบอย่างมาก \(\lceil \log_2 n\rceil\) ครั้ง หรือ \(O(\log n)\)
ข้อสังเกต
Binary search สามารถใช้ได้กับข้อมูลที่มีการเรียงแล้วเท่านั้น
Binary Search กับ Competitive Programming
โจทย์ตัวอย่าง
รับจำนวนเต็มมา \(n\) จำนวน \(a_1, a_2, ..., a_n\) โดยที่ \(a_i \leq a_{i+1}\) สำหรับ \(1 \leq i \leq n-1\)
ต้องการถาม \(q\) คำถาม ในคำถามที่ \(i\) ให้ตอบว่ามีกี่ตัวเลขใน \(n\) ตัวเลขนี้ ที่มีค่าอยู่ระหว่าง \(x_i\) และ \(y_i\) โดยที่ constraints เป็นดังนี้
\(1 \leq n, q \leq 100,000\)
\(1 \leq a_1, ..., a_n \leq 10^9\)
สังเกตว่า ในโจทย์ข้อนี้ ถ้าหากตรวจสอบทุกตัวเลข ในแต่ละคำถาม จะใช้เวลา \(O(nq)\) ซึ่งไม่พอต่อขอบเขตข้อมูลของโจทย์
เราสามารถหาว่า มีเลขกี่ตัวที่น้อยกว่าหรือเท่ากับ \(A\) ได้ ใน \(O(\log n)\) ด้วย binary search โดย:
- กำหนดตำแหน่งข้อมูลที่น้อย และมากที่สุดที่เป็นไปได้ (ให้ \(L=0,R=n\))
- หาค่าตรงกลาง ระหว่าง \(L\) กับ \(R\) ให้ค่านี้เป็น \(mid\)
- ตรวจสอบข้อมูลในตำแหน่ง \(mid\)
- ถ้าเกิดข้อมูลน้อยกว่าหรือเท่ากับเลขที่เราค้นหา ให้ค่า \(L = mid+1\)
- ถ้าเกิดไม่ใช่ ให้ค่า \(R = mid\) (ในที่นี้ เราจะไม่ใช้ \(R=mid-1\) ในการเปลี่ยนค่า เพราะอาจมีข้อมูลซ้ำหลายๆ ที่ได้ แล้วเราต้องการตำแหน่งที่อยู่ขวาสุด)
- ทำซ้ำไปเรื่อยๆ จนกว่า \(L = R\)
- จะได้ว่า \(L\) เป็นตำแหน่งของเลขตัวแรก ที่มีค่ามากกว่า \(A\) ดังนั้นจำนวนเลขกี่ตัวที่น้อยกว่าหรือเท่ากับ \(A\) มี \(L\) จำนวน
ข้อสังเกต
การ binary search ในที่นี้ จะมีลักษณะเหมือนฟังก์ชั่น std::upper_bound และ std::lower_bound ในภาษา C++ ดังนั้นสามารถใช้ฟังก์ชั่นนี้โดยตรงได้เลย (จริงๆ แล้ว ทั้งสองฟังก์ชั่นใช้ binary search ในการค้นหาตำแหน่ง)
ในการแก้โจทย์ข้อนี้ เราจะหาตำแหน่งของ 2 ตัวเลข คือ จำนวนตัวเลขที่น้อยกว่าหรือเท่ากับ \(x_i-1\) (ให้ค่าเป็น \(P\)) และจำนวนตัวเลขที่น้อยกว่าหรือเท่ากับ \(y_i\) (ให้ค่าเป็น \(Q\)) สำหรับแต่ละคำถาม สามารถตอบ \(Q-P\) ได้เลย
สรุป Time complexity:
- การรับข้อมูล: \(O(n)\)
- ถามแต่ละคำถาม: \(O(\log n) \rightarrow\) ถาม 2\(q\) ครั้ง จะได้ time complexity เป็น \(O(q \log n)\)
Time complexity รวม: \(O(n+q \log n)\) ซึ่งเพียงพอต่อความต้องการของโจทย์
ตัวอย่างโค้ด (ไม่ใช้ std::upper_bound)
#include <bits/stdc++.h>
using namespace std;
int n, q, arr[100001];
int search(int num) {
int l = 0, r = n;
while(l < r) {
int mid = (l+r)/2;
if(arr[mid] <= num) {
l = mid+1;
} else {
r = mid;
}
}
return l;
}
int main() {
cin >> n >> q;
for(int i=0; i<n; i++) {
cin >> arr[i];
}
sort(arr, arr+n);
for(int i=0; i<q; i++) {
int a, b;
cin >> a >> b;
cout << search(b) - search(a-1) << "\n";
}
}
ข้อผิดพลาดที่เกิดขึ้นบ่อย
- การที่เราหาค่า mid โดยการใช้สมการ \((L+R)/2\) อาจทำให้เกิด overflow ขึ้นได้ เพราะระหว่างการคำนวณ ค่า \((L+R)\) จะมีค่ามากกว่าทั้งค่า L และ R ที่โจทย์กำหนด โดยสามารถแก้ได้โดยการใช้สมการ \(L + (R-L)/2\)
ตัวอย่างโค้ด (ใช้ std::upper_bound)
#include <bits/stdc++.h>
using namespace std;
int n, q, arr[100001];
int main() {
int n, q;
cin >> n >> q;
for(int i=0; i<n; i++) {
cin >> arr[i];
}
sort(arr, arr+n);
for(int i=0; i<q; i++) {
int x, y;
cin >> x >> y;
cout << upper_bound(arr, arr+n, y) - upper_bound(arr, arr+n, x-1) << "\n";
}
}
คำแนะนำ
ถ้าเกิดข้อมูลไม่ได้เรียงมาให้ กล่าวคือ \(a_i \leq a_{i+1}\) ไม่เป็นจริงเสมอไป สามารถจัดเรียงข้อมูลโดยใช้ std::sort (หรืออาจเป็นฟังก์ชั่นอื่นในภาษาอื่น) ก่อน เพื่อทำขึ้นตอนต่อไปได้ ซึ่งมี Time complexity เป็น \(O(n \log n)\)
| Problem | Source | Difficulty | Solution |
|---|---|---|---|
| Interesting drink | CF | Easy | View |
| สารคดีออนไลน์ (NBK48) | TOI | Normal | View |
| เชียงใหม่ไน่ทรัพย์ (Shopping) | TOI | Normal | View |
| Coloring game | CF | Normal | View |
Binary search on answer
โจทย์ตัวอย่าง: กุลีแห่งท่าเรือ - การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 11
โจทย์โดยย่อ: มีกุลีทั้งหมด \(m\) คน กุลีคนที่ \(i\) จะใช้เวลา \(t_i\) นาที ในการขนสินค้า 1 ชิ้นขึ้นเรือ อยากทราบว่า ถ้าต้องการขนสินค้า \(n\) ชิ้นขึ้นเรือ โดยใช้กุลีทั้ง \(m\) คน จะใช้เวลาน้อยที่สุดเท่าไหร่ โดยมี constraints ดังนี้
\(2\leq m\leq 10^6\)
\(1\leq n\leq 10^{12}\)
\(1\leq t_i\leq 10^6\) สำหรับ \(1\leq i\leq m\)
ถ้าเกิดลองเปลี่ยนโจทย์ จากหาเวลาที่น้อยที่สุด เป็น จงหาว่า เวลา \(k\) นาที สามารถนำสินค้าขึ้นเรือทันหรือไม่ จะเป็นโจทย์ที่ง่ายขึ้นมาก สามารถแก้ได้ใน \(O(m)\) โดยกุลีคนที่ \(i\) สามารถขนสินค้าได้ \(\lfloor \frac{k}{t_i}\rfloor\) ชิ้น ตามโค้ดด้านล่าง (ให้ arr[i] แทนค่า \(t_i\))
กลับมาที่โจทย์เดิม สังเกตว่าถ้า \(sum >= m\) จะได้ว่าเวลาที่น้อยที่สุด จะน้อยกว่าหรือเท่ากับ \(k\) เสมอ และถ้า \(sum < m\) จะได้ว่าเวลาที่น้อยที่สุด จะมากกว่า \(k\) เสมอ
ถ้าเกิดให้เวลาที่น้อยที่สุดที่สามารถขนสินค้าขึ้นเรือทัน เป็น \(ans\) จะได้ว่า \(ans+1\), \(ans+2\), ... ก็ขนสินค้าขึ้นเรือทันเหมือนกัน ในขณะเดียวกัน \(ans-1\), \(ans-2\), ... ก็จะขนสินค้าขึ้นเรือไม่ทัน เราสามารถทำการ binary search หาค่า \(ans\) นี้ได้เลย
อย่างแรก ต้องกำหนดค่าน้อยที่สุดและค่ามากที่สุดก่อน คำตอบที่น้อยที่สุดคือ \(1\) และคำตอบที่มากที่สุดคือ \(n\min(t_i)\) โดยจาก \(1\leq n\leq 10^{12}\) และ \(1\leq t_i\leq 10^6\) จะได้ว่าค่ามากที่สุดคือ \(10^{18}\)
หลักการก็จะเหมือนกับ binary search โดยตรง ดังนี้
- กำหนดตำแหน่งข้อมูลที่น้อย และมากที่สุดที่เป็นไปได้ (ให้ \(L=1,R=10^{18}\))
- หาค่าตรงกลาง ระหว่าง \(L\) กับ \(R\) ให้ค่านี้เป็น \(mid\)
- ตรวจสอบข้อมูลในตำแหน่ง \(mid\)
- ถ้าเวลา \(mid\) สามารถขนสินค้าขึ้นเรือทัน จะได้ว่า คำตอบจะต้องมีค่า \(<=mid\) จึงให้ \(R=mid\)
- ถ้าเวลา \(mid\) ไม่สามารถขนสินค้าขึ้นเรือได้ทัน จะได้ว่า คำตอบจะต้องมีค่า \(>mid\) จึงให้ \(L=mid+1\)
- ทำซ้ำไปเรื่อยๆ จนกว่า \(L = R\)
- จะได้ว่า \(L\) เป็นคำตอบที่เราต้องการ จึงสามารถนำค่า \(L\) มาตอบได้เลย
ฟังก์ชันโมโนโทน
ถ้าเกิดเรานิยาม \(f(x)\) เป็นฟังก์ชัน โดยที่ \(f(x)\) จะเป็นจริงก็ต้องเมื่อเวลา \(x\) นาที สามารถขนของได้ทัน และเป็นเท็จก็ต่อเมื่อ เวลา \(x\) นาทีขนของไม่ทัน จะสังเกตได้ว่า \(f(x)\) จะเป็นเท็จตลอด จนกว่าจะถึงจุดๆ หนึ่ง จากนั้นจะเป็นจริงตลอด เราเรียกสมบัตินี้ว่า โมโทโทน
ฟังก์ชันโมโนโทน คือฟังก์ชันที่ไม่เพิ่ม หรือ ไม่ลด อย่างใดอย่างหนึ่ง ในการทำ binary search on answer ฟังก์ชันควรจะเป็นโมโนโทน ถึงจะสามารถใช้ได้
แน่นอนว่าอาจมีฟังก์ชันแบบอื่นๆ เช่น เป็นเท็จก่อนแล้วค่อยจริง
ตัวอย่าง
กุลี 2 คน: \(t = [7, 12]\), ต้องขน \(n = 5\) ชิ้น
กำหนด \(L = 1\), \(R = 5\times 7 = 35\) (เพราะ \(\min t_i = 7\))
- mid = 18: ขนได้ \(\lfloor18/7\rfloor+\lfloor18/12\rfloor = 2+1=3 < 5\) (ยังไม่พอ) ⇒ \(L = 19\)
- mid = 22: ขนได้ \(\lfloor22/7\rfloor+\lfloor22/12\rfloor = 3+1=4 < 5\) (ยังไม่พอ) ⇒ \(L = 23\)
- mid = 29: ขนได้ \(\lfloor29/7\rfloor+\lfloor29/12\rfloor = 4+2=6 \geq 5\) (หาค่าที่ดีกว่า) ⇒ \(R = 29\)
- mid = 26: ขนได้ \(\lfloor26/7\rfloor+\lfloor26/12\rfloor = 3+2=5 \geq 5\) (หาค่าที่ดีกว่า) ⇒ \(R = 26\)
- mid = 24: ขนได้ \(\lfloor24/7\rfloor+\lfloor24/12\rfloor = 3+2=5 \geq 5\) (หาค่าที่ดีกว่า) ⇒ \(R = 24\)
- mid = 23: ขนได้ \(\lfloor23/7\rfloor+\lfloor23/12\rfloor = 3+1=4 < 5\) (ยังไม่พอ) ⇒ \(L = 24\)
สรุป \(L = R = 24\) คำตอบคือ 24 นาที
Time Complexity ของวิธีนี้ จะได้ว่า ในตรวจสอบ 1 ครั้งใช้เวลา \(O(m)\) และจะทำการรันฟังก์ชันทั้งหมด \(\log (n\min(t_i))\) ครั้ง ทำให้ Time complexity รวมเป็น \(O(m \log (n\min(t_i)))\) หรือประมาณ \(O(m \log n)\) ซึ่งเพียงพอต่อความต้องการของโจทย์
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
long long n, m, arr[1000010], l=1, r=1e18, mid; // ให้ค่า R เป็น 10^18 ไปเลย
long long find_sum(long long k) {
long long sum = 0;
for(int i=1; i<=m; i++) {
sum += k/arr[i];
}
return sum;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> m >> n;
for(int i=1; i<=m; i++) {
cin >> arr[i];
}
while(l < r) {
mid = (l+r)/2;
if(find_sum(mid) < n) {
l = mid+1;
} else {
r = mid;
}
}
cout << l;
return 0;
}
คำเตือน
- ควรตรวจสอบดีๆ ว่าโค้ดเกิดการ overflow หรือไม่ เช่น ถ้าเกิด \(t_i\leq 10^{18}\) โค้ดข้างต้นอาจทำให้เกิด overflow ได้
- ควรคิดถึงเคสพิเศษ ก่อนลงมือเขียนโค้ด เช่น \(n=0, m=0\) (ซึ่งในโจทย์ข้อนี้ไม่มี)
| Problem | Source | Difficulty | Solution |
|---|---|---|---|
| Factory Machine | CSES | Easy | View |
| ห้องสมุดเมือง 3M | สอวน. | Easy | View |
| Jump | PROG | Normal | View |
| Multiplication table | CSES | Normal | View |
| Merge | TOI | Normal | View |
| Max Median | CF | Hard | View |
| Evergreen | สสวท. | Hard | View |