แผนการเรียน
/

Binary Search Implementation
จากทฤษฎีสู่การเขียนโค้ดจริง

ช่วงบ่าย (13.00 - 15.00): เจาะลึกการ 구현 บนอาเรย์และคำตอบ

สิ่งที่เราจะทำในเซสชันนี้

1
เขียนโค้ด Binary Search 2 รูปแบบมาตรฐาน
2
ฝึกใช้ STL lower_bound เพื่อลดเวลาเขียนโค้ด
3
Implementation: Binary Search on Answer สำหรับโจทย์ Optimization

ทบทวน: กระบวนการ Binary Search

อัลกอริทึมจะทำการตรวจสอบค่าที่ "จุดกึ่งกลาง" ของขอบเขตการค้นหาเสมอ

ถ้าค่ากึ่งกลางคือคำตอบ

หยุดการทำงานและคืนค่าตำแหน่งนั้นทันที

ถ้าไม่ใช่คำตอบ

เลื่อนขอบเขต (low หรือ high) เพื่อทิ้งข้อมูลครึ่งหนึ่งที่ไม่เกี่ยวข้อง

"ข้อมูลต้องเรียงลำดับเสมอ (Sorted Array)"

Implementation 1: while (low <= high)

int low = 0, high = n - 1;
while (low <= high) {
  int mid = low + (high - low) / 2;
  if (array[mid] == x) return mid; // พบคำตอบ
  if (array[mid] > x) high = mid - 1;
  else low = mid + 1;
}
return -1;

ในวิธีนี้ ขอบเขตจะถูกบีบเข้าหากันจน low > high จึงจบการทำงาน

ทำไมไม่ใช้ (low + high) / 2?

low + high อาจทำให้เกิด Integer Overflow

ควรใช้: low + (high - low) / 2

เป็นแนวทางปฏิบัติที่ช่วยให้โค้ดของคุณปลอดภัยแม้ข้อมูลจะมีขนาดใหญ่ถึง \(10^9\)

Implementation 2: Jump Method

int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
  while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) { // พบคำตอบที่ตำแหน่ง k }

แนวคิดคือการ "กระโดด" ไปข้างหน้าด้วยระยะทางที่ลดลงทีละครึ่ง

ข้อดี: เขียนง่าย ลดข้อผิดพลาดเรื่อง index นอกขอบเขต (Out of bounds)

อย่าเขียนเองถ้าไม่จำเป็น!

C++ มีฟังก์ชันที่มีประสิทธิภาพสูงให้ใช้อยู่แล้วใน <algorithm>

lower_bound

หาตัวแรกที่ ค่า \(\ge x\)

upper_bound

หาตัวแรกที่ ค่า \(> x\)

"ประหยัดเวลาและลดโอกาสเกิด Bug ในการแข่งขัน"

Counting Elements with STL

auto a = lower_bound(arr, arr+n, x);
auto b = upper_bound(arr, arr+n, x);
cout << b - a << "\n"; // จำนวนครั้งที่ x ปรากฏในอาเรย์

การใช้ b - a ทำได้เพราะ STL คืนค่าเป็น Iterators

*หมายเหตุ: อาเรย์ต้องถูกเรียงลำดับก่อนเสมอ

Binary Search on Answer

ใช้เมื่อเราต้องการหาค่า \(k\) ที่น้อยที่สุดหรือมากที่สุดที่ เป็นไปได้

เงื่อนไขที่ต้องมี:

ต้องมีฟังก์ชัน ok(x) ที่มีความเป็น Monotone (เช่น ถ้า \(x\) ใช้ได้ ทุกค่าที่มากกว่า \(x\) ก็ต้องใช้ได้)

The Decision Function

bool ok(long long x) {
  // ลอจิกตรวจสอบว่าคำตอบ x "ใช้ได้" หรือไม่
  // มักจะใช้ Greedy หรือการวนลูปเช็คพื้นฐาน O(N)
  if (is_valid) return true;
  return false;
}

"ความซับซ้อนรวมจะเป็น \(O(N \log Z)\)[เมื่อ \(Z\) คือขอบเขตคำตอบ"

Finding Smallest k

long long x = -1;
for (long long b = z; b >= 1; b /= 2) {
  while (!ok(x + b)) x += b;
}
long long k = x + 1; // k คือคำตอบที่น้อยที่สุด

โค้ดนี้จะหาค่า \(x\) ที่ใหญ่ที่สุดที่ ok(x) เป็นเท็จ แล้วบวกเพิ่มอีก 1

กรณีศึกษา: การตัดไส้กรอก

มีไส้กรอก \(N\) ชิ้นยาวต่างกัน ต้องการตัดให้ได้ \(M\) ชิ้นยาวเท่ากัน โดยยาวที่สุดที่เป็นไปได้

แนวทางการ 구현:

  • แทนที่จะหาค่าสูงสุดตรงๆ ให้สร้างฟังก์ชัน ok(len)
  • ok(len): เช็คว่าถ้าตัดยาว len จะได้ไส้กรอก \(\ge M\) ชิ้นหรือไม่
  • ใช้ Binary Search บีบช่วงความยาว

BS on Real Numbers

for (int i = 0; i < 100; i++) {
  double mid = (lo + hi) / 2;
  if (ok(mid)) lo = mid;
  else hi = mid;
}

ทำไมต้องวน 100 รอบ?

เพื่อให้ได้ความแม่นยำสูงสุด (Precision) และปลอดภัยจากการวนลูปไม่รู้จบ (Infinite loop)

Precision Warning!

"double มีความละเอียดเพียงประมาณ 15-17 หลัก"

การใช้ while (hi - lo > 1e-9) อาจเกิดปัญหากับคำตอบที่มีค่าขนาดใหญ่มาก

ใช้ Fixed Iterations (เช่น 100 รอบ) เสมอในการแข่งขัน

นอกเหนือจากอาเรย์

Searching on Functions:

หาค่าสูงสุด/ต่ำสุดของฟังก์ชันที่มีความต่อเนื่อง (Monotonic Functions)

Finding Invariants:

ใช้เพื่อตรวจสอบคุณสมบัติที่ไม่เปลี่ยนแปลงในระหว่างกระบวนการแก้ปัญหา

Exercise 1: Basic

"Implement Search in Sorted Array"

เขียนฟังก์ชัน Binary Search ของคุณเองและเปรียบเทียบกับ std::lower_bound

Constraint: N = 10^6, T = 1s

Exercise 2: Advanced

"Minimize Maximum (Minimax)"

จงหาค่าที่น้อยที่สุดที่เป็นไปได้ของค่าที่มากที่สุดจากชุดข้อมูล (โจทย์แนวการแบ่งงาน)

"Hint: ใช้ Binary Search on Answer"

เทคนิคการหา Bug ใน Binary Search

1. Print Mid: แสดงค่า mid และผลของ ok(mid) ในทุกรอบ

2. Test Edge Cases: ทดสอบกับ \(N=0, 1\) หรือกรณีที่ไม่มีคำตอบ

3. Local Testing: ใช้ไฟล์ input.txt และ output.txt เพื่อความรวดเร็ว

แหล่งฝึกฝนเพิ่มเติม

CSES Problem Set

ส่วนของ Sorting and Searching ที่แนะนำโดยผู้เชี่ยวชาญ

Codeforces

ค้นหา Tag: 'binary search' เพื่อโจทย์ระดับสากล

"การทำโจทย์ย้อนหลังคือวิธีพัฒนาที่เร็วที่สุด (Up-solving)"

Key Takeaways

การ 구현 ต้องระวัง Integer Overflow ใน mid
STL คือเครื่องมือที่ทรงพลังและแม่นยำที่สุด
Binary Search on Answer เปลี่ยนปัญหา Optimization เป็นการตัดสินใจ
ใช้ Fixed Iterations กับเลขทศนิยมเสมอ

Coding Session

15.00 - 17.00 น.

Practice: Binary Search Problems

"โค้ดของคุณคือคำตอบที่ดีที่สุด" เจอกันในแล็บครับ!