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

Day 02: Practice Session
Binary Search Mastery

เวลา 15.00 - 17.00 น.: ฝึกทักษะการค้นหาและการหาค่าที่เหมาะสมที่สุด

รายการโจทย์สำหรับการฝึก

1. Basic Search: ค้นหาค่าใน Sorted Array
2. Frequency Count: ใช้ STL หาจำนวนตัวเลข
3. 2SUM (Sorted): หาคู่บวกด้วยการค้นหา
4. Cutting Hot Dogs: BS on Answer พื้นฐาน
5. Ballot Boxes: โจทย์ Optimization
6. Square Root: BS บนจำนวนจริง

Problem 1: Search in Sorted Array

โจทย์: ให้ Sorted Array ขนาด \(N\) และค่า \(X\) จงหาตำแหน่ง (Index) ของ \(X\) ถ้าไม่พบให้ตอบ -1 .

Input: N=5, Array=[3-7], X=7
Output: 3

Step-by-Step Logic

1 กำหนด low = 0, high = N-1 .
2 คำนวณ mid = low + (high-low)/2 เพื่อป้องกัน Overflow .
3 ถ้า arr[mid] == X ตอบ mid, ถ้า < X เลื่อน low, ถ้า > X เลื่อน high .

Problem 2: Counting Elements

โจทย์: ใน Sorted Array มีเลข \(X\) ปรากฏอยู่กี่ครั้ง? .

Input: Array=[3, 5, 10, 11], X=2
Output: 3 (ตำแหน่งที่ 1 ถึง 3)

Step-by-Step Logic (STL Approach)

1 ใช้ std::lower_bound หาตำแหน่งแรกที่ค่า \(\ge X\) .
2 ใช้ std::upper_bound หาตำแหน่งแรกที่ค่า \(> X\) .
auto it1 = lower_bound(v.begin(), v.end(), X);
auto it2 = upper_bound(v.begin(), v.end(), X);
cout << it2 - it1; // คำตอบคือระยะห่างระหว่าง iterator

Problem 3: 2SUM Problem

โจทย์: กำหนด Sorted Array และเป้าหมาย \(T\) จงหาว่ามีคู่ตัวเลขสองตัวที่บวกกันได้ \(T\) หรือไม่ , .

Input: Array=[3, 5-7, 14, 15], T=12
Output: YES (5 + 7)

Step-by-Step Logic

1 วนลูป for เพื่อเลือกตัวเลขตัวแรก arr[i] .
2 คำนวณค่าที่ต้องการหาคือ target = T - arr[i] .
3 ใช้ Binary Search ค้นหา target ในส่วนที่เหลือของอาเรย์ .

Complexity: \(O(N \log N)\)

Optimization Challenge

Problem: Cutting Hot Dogs

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

Hint: ถ้าตัดยาว \(L\) ได้ชิ้นครบ ความยาวที่น้อยกว่า \(L\) ก็ต้องได้ครบ (Monotonic) .

Binary Search on Answer

bool ok(double L) {
  long long count = 0;
  for (auto x : rods) count += floor(x / L);
  return count >= M; // ตัดได้ครบ M คนไหม
}
Algorithm: ทำ Binary Search บนช่วง [0, \(10^6\)] โดยใช้ฟังก์ชัน ok(L) ตรวจสอบค่ากลาง , .

Problem 5: Ballot Boxes (Kattis)

มีเมือง \(N\) เมือง แต่ละเมืองมีประชากร \(P_i\) และมีหีบบัตรเลือกตั้ง \(B\) หีบ (\(B \ge N\)) ต้องกระจายหีบให้ทุกเมือง (อย่างน้อยเมืองละ 1) โดยต้องการให้ จำนวนประชากรสูงสุดต่อหนึ่งหีบ มีค่าน้อยที่สุด .

"Minimize the Maximum" - โจทย์แนวมาตรฐานของ Binary Search on Answer.

Step-by-Step Logic

1 กำหนด ok(K): ถ้าให้แต่ละหีบรับได้สูงสุด \(K\) คน จะใช้หีบรวมกันไม่เกิน \(B\) หรือไม่?
2 คำนวณหีบที่ใช้: needed = sum(ceil(P_i / K))
3 ถ้า needed <= B แปลว่าค่า \(K\) นี้ใช้ได้ ให้ลองหาค่าที่น้อยกว่านี้ .

Problem 6: Finding Square Root

โจทย์: จงหาค่า \(\sqrt{N}\) โดยไม่ใช้ฟังก์ชันสำเร็จรูป ให้ตอบเป็นทศนิยมแม่นยำ \(10^{-7}\) .

ข้อควรระวัง: การเปรียบเทียบเลขทศนิยมโดยตรงอาจเกิด Infinite Loop ให้ใช้การวนลูปคงที่ 100 รอบแทน .

Step-by-Step Logic

double lo = 0, hi = N;
for (int i = 0; i < 100; i++) { // Fixed iterations
  double mid = (lo + hi) / 2.0;
  if (mid * mid <= N) lo = mid;
  else hi = mid;
}
cout << fixed << setprecision(7) << lo;

ความลับของคนเก่ง: Up-solving

"หากข้อไหนทำไม่ได้ภายใน 20 นาที ให้หยุดอ่านเฉลย ทำความเข้าใจ แล้วกลับมา เขียนโค้ดใหม่ด้วยตัวเอง (Up-solve)" .

เทคนิคนี้ช่วยพัฒนาImplementation skills ได้เร็วที่สุดเมื่อเริ่มต้น .

เจอกันพรุ่งนี้กับเรื่อง: STL Containers & Data Structures!