Binary Search — The 100,000 Questions Problem
This lesson is one problem again. This time your first program will be correct — and still not good enough. Bài này lại là một bài toán. Lần này chương trình đầu tiên của bạn sẽ đúng — nhưng vẫn chưa đủ tốt.
🎯 Section 1 — The Problem
A small online contest has 5 contestants. Each one scored some points. Contestants send the organisers questions like "did anybody score exactly 512?" Một cuộc thi trực tuyến nhỏ có 5 thí sinh, mỗi bạn được một số điểm. Thí sinh gửi câu hỏi cho ban tổ chức, ví dụ "có ai được đúng 512 điểm không?"
Your job: for each question x, write YES into out.txt if some contestant scored exactly x, otherwise NO. Nhiệm vụ: với mỗi câu hỏi x, ghi YES vào out.txt nếu có thí sinh được đúng x điểm, nếu không thì ghi NO.
Two files, one number per line: Hai tệp, mỗi dòng một số:
- points-5.txt — the points of 5 contestants:
734 205 918 512 367. điểm của 5 thí sinh. - questions-5.txt — 5 questions:
512 100 918 640 205. 5 câu hỏi.
Try it first / Hãy thử trước
You already know everything you need: read both files, and for each question look through the points. Write the program yourself before you open the answer. Bạn đã biết mọi thứ cần dùng: đọc cả hai tệp, rồi với mỗi câu hỏi hãy xem qua các điểm. Tự viết chương trình trước khi mở đáp án.
Save it as find_number.cpp, then compile and run it: Lưu với tên find_number.cpp, rồi biên dịch và chạy:
bashg++ -o find_number find_number.cpp ./find_number
Your out.txt should be exactly this: Tệp out.txt của bạn phải đúng như sau:
YES
NO
YES
NO
YESThis program is correct. Keep it — you will use it again. Chương trình này đúng. Hãy giữ lại — bạn sẽ dùng lại nó.
📈 Section 2 — Grow the Input
The contest grows. First 20,000 contestants send 20,000 questions. Then comes the national round: 100,000 contestants, each scoring between 0 and 1,000,000 points, sending 100,000 questions. Run the same program on each size. Cuộc thi lớn dần. Đầu tiên 20.000 thí sinh gửi 20.000 câu hỏi. Rồi đến vòng toàn quốc: 100.000 thí sinh, mỗi bạn được từ 0 đến 1.000.000 điểm, gửi 100.000 câu hỏi. Chạy cùng chương trình với từng cỡ.
Download the data / Tải tệp dữ liệu
points-20000.txt and questions-20000.txt — 20,000 contestants, 20,000 questions. 20.000 thí sinh, 20.000 câu hỏi.
points-100k.txt and questions-100k.txt — 100,000 contestants, 100,000 questions. 100.000 thí sinh, 100.000 câu hỏi.
- In your program, change
"points-5.txt"to"points-20000.txt"and"questions-5.txt"to"questions-20000.txt". Save, compile withg++again, and run./find_number. It finishes — but you have to wait. Trong chương trình, đổi tên hai tệp thành bản 20000. Lưu, biên dịch lại bằng g++, rồi chạy ./find_number. Chương trình chạy xong — nhưng bạn phải chờ. - Now change both names to the
100kfiles, compile and run again. Wait. It takes a very long time — half a minute or more. Giờ đổi cả hai tên sang tệp 100k, biên dịch rồi chạy lại. Chờ. Chương trình chạy rất lâu — nửa phút hoặc hơn.
Stop a program with Ctrl+C / Dừng chương trình bằng Ctrl+C
Click the Git Bash window and press Ctrl+C. The program stops and the $ comes back. Use it whenever a program seems stuck. Bấm vào cửa sổ Git Bash rồi nhấn Ctrl+C. Chương trình dừng và dấu $ hiện lại. Dùng nó mỗi khi chương trình có vẻ bị treo.
Nothing is wrong with the program — it gives the right answers, eventually. But in a contest the judge gives your program 1 second. A correct program that is too slow scores zero. Chương trình không sai — cuối cùng nó ra đáp án đúng. Nhưng trong cuộc thi, máy chấm chỉ cho chương trình 1 giây. Chương trình đúng mà quá chậm vẫn được 0 điểm.
🧮 Section 3 — Count the Work
How slow is it, exactly? Start small and count by hand. Watch the program answer the 5 questions from Section 1, and count how many times it compares a point with a question. Chậm đến mức nào? Bắt đầu nhỏ và tự đếm. Xem chương trình trả lời 5 câu hỏi ở Phần 1, và đếm xem nó so sánh một điểm với một câu hỏi bao nhiêu lần.
points-5.txt. The program asks 5 questions, and each question checks every point. 5 điểm trong points-5.txt. Chương trình hỏi 5 câu, mỗi câu kiểm tra mọi điểm.Now make the program count its own work: add int steps = 0; at the start of main, add 1 every time it compares a point with a question, and print steps at the end. Giờ cho chương trình tự đếm: thêm int steps = 0; ở đầu main, cộng 1 mỗi lần so sánh một điểm với một câu hỏi, và in steps ở cuối.
cpp#include <iostream> #include <fstream> #include <vector> using namespace std; int main() { int steps = 0; ifstream fin("points-5.txt"); vector<int> points; int p; while (fin >> p) { points.push_back(p); } ifstream qin("questions-5.txt"); vector<int> questions; int q; while (qin >> q) { questions.push_back(q); } ofstream fout("out.txt"); for (int x : questions) { bool found = false; for (int point : points) { steps = steps + 1; if (point == x) { found = true; } } if (found) { fout << "YES" << endl; } else { fout << "NO" << endl; } } cout << steps << endl; return 0; }
Run it on the small files. It prints 25 — the same number you counted. Chạy với tệp nhỏ. Nó in 25 — đúng số bạn vừa đếm.
Now run it on the 20,000 files, then work out the 100,000 case — do not run that one: steps would grow too big for an int. Giờ chạy với tệp 20.000, rồi tính trường hợp 100.000 — đừng chạy trường hợp đó: steps sẽ lớn quá sức chứa của int.
- 5 × 5 = 25 steps. 25 bước.
- 20,000 × 20,000 = 400,000,000 steps — the few seconds you waited. 400.000.000 bước — vài giây bạn đã chờ.
- 100,000 × 100,000 = 10,000,000,000 steps. 10.000.000.000 bước.
Estimate before you code / Ước lượng trước khi viết code
A handy rule: C++ does about 100 million simple steps per second. So 400,000,000 steps take a few seconds — what you saw. And 10,000,000,000 steps take about 100 seconds. The program is right, but it is 100 times too slow. (The same program in Python is about 10 times slower again — that is why most contest players use C++.) Quy tắc dễ nhớ: C++ làm khoảng 100 triệu bước đơn giản mỗi giây. Vậy 400.000.000 bước mất vài giây — đúng như bạn thấy. Còn 10.000.000.000 bước mất khoảng 100 giây. Chương trình đúng, nhưng chậm gấp 100 lần. (Cùng chương trình đó viết bằng Python còn chậm hơn khoảng 10 lần nữa — vì vậy phần lớn người thi lập trình dùng C++.)
🧩 Section 4 — The Real Problem
The slow program finds a number the only way it knows: it checks the points one at a time, from the first to the last. With 100,000 points, one question can take 100,000 checks. Chương trình chậm tìm một số theo cách duy nhất nó biết: kiểm tra từng điểm một, từ đầu đến cuối. Với 100.000 điểm, một câu hỏi có thể mất 100.000 lần kiểm tra.
The problem / Bài toán
We need a better way to find a number than checking every number, one at a time. Cần một cách tìm một số tốt hơn là kiểm tra từng số một.
Before any code, play a game. Trước khi viết code, hãy chơi một trò chơi.
🎲 Section 5 — The Guessing Game
The computer is thinking of a number from 1 to 100. Click a number to guess it. After each guess it tells you higher or lower, so you always know which numbers are still possible. Find the number in as few guesses as you can, then press New game — every game has a new number. Máy đang nghĩ một số từ 1 đến 100. Bấm vào một số để đoán. Sau mỗi lần đoán, máy cho bạn biết lớn hơn hay nhỏ hơn, nên bạn luôn biết những số nào vẫn còn có thể. Hãy tìm ra số đó với ít lần đoán nhất có thể, rồi bấm New game — mỗi ván là một số mới.
Play as many games as you like. How many guesses did each game take? Is there a way that always finds the number quickly, whatever it is? Chơi bao nhiêu ván tùy thích. Mỗi ván bạn cần bao nhiêu lần đoán? Có cách nào luôn tìm ra số đó nhanh, dù số đó là gì không?
💡 Section 6 — The Best Strategy
The best strategy: always guess the middle of what is still possible. Then every answer throws away half. Halve 100 numbers until only 1 is left, counting each halving: Cách hay nhất: luôn đoán số ở giữa những số còn có thể. Khi đó mỗi câu trả lời loại đi một nửa. Chia đôi 100 số cho tới khi chỉ còn 1, đếm từng lần chia đôi:
7 halvings, so 7 guesses are always enough. For 1 to 1,000,000 you need only 20. 7 lần chia đôi, nên 7 lần đoán luôn là đủ. Với 1 đến 1.000.000 chỉ cần 20 lần.
Why it works / Vì sao cách này hiệu quả
"Higher" throws away every smaller number only because the numbers are in order. To play this game with the contestants' points, the points must be sorted first — the tool from the last lesson. You sort once, then answer every question. "Lớn hơn" loại được mọi số nhỏ hơn chỉ vì các số đã có thứ tự. Muốn chơi trò này với điểm của thí sinh, phải sắp xếp điểm trước — công cụ của bài trước. Sắp xếp một lần, rồi trả lời mọi câu hỏi.
🔍 Section 7 — Binary Search
The guessing game, written as a function. It works on a sorted vector: Trò chơi đoán số, viết thành một hàm. Nó làm việc trên một vector đã sắp xếp:
lois the first position that could still holdx,hithe last. lo là vị trí đầu tiên còn có thể chứa x, hi là vị trí cuối.midis the guess — the position halfway between them. Dividing oneintby another drops what is after the decimal point:7 / 2is3. mid là lần đoán — vị trí ở giữa. Chia một int cho một int sẽ bỏ phần thập phân: 7 / 2 là 3.- If
points[mid]is too small,xcan only be to the right:lo = mid + 1. Too big:hi = mid - 1. Nếu points[mid] nhỏ quá, x chỉ có thể ở bên phải: lo = mid + 1. Lớn quá: hi = mid - 1. - When
lopasseshi, nothing is left to look at —xis not there. Khi lo vượt qua hi, không còn gì để xem — x không có trong vector.
lo starts at the first position, hi at the last. 50 điểm đã sắp xếp. 738 có trong đó không? lo bắt đầu ở vị trí đầu, hi ở vị trí cuối.That is the idea. Here is the same search written as code — a function we call contains. Each press of Next runs one line, so you can watch lo, hi and mid change, the same way they moved in the grid above. First we look for 760, a score someone has; then press x = 603 to look for a score nobody has. Đó là ý tưởng. Đây là cùng cách tìm đó, viết thành code — một hàm ta gọi là contains. Mỗi lần bấm Next chạy một dòng, nên bạn thấy lo, hi và mid thay đổi, giống như chúng đã di chuyển trong bảng số ở trên. Đầu tiên ta tìm 760, một điểm có người đạt; rồi bấm x = 603 để tìm một điểm không ai đạt.
contains(points, 760) — no line has run yet. Ta hỏi: 760 có trong 100 điểm đã sắp xếp không? Đó là lời gọi contains(points, 760) — chưa có dòng nào chạy.The whole program — it sorts the points once, then asks contains for every question. Write it in a new file, fast.cpp, and keep find_number.cpp. Toàn bộ chương trình — sắp xếp điểm một lần, rồi gọi contains cho mỗi câu hỏi. Viết vào tệp mới fast.cpp, và giữ lại find_number.cpp.
cpp#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; bool contains(const vector<int>& points, int x) { int lo = 0; int hi = points.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (points[mid] == x) { return true; } if (points[mid] < x) { lo = mid + 1; } else { hi = mid - 1; } } return false; } int main() { ifstream fin("points-5.txt"); vector<int> points; int p; while (fin >> p) { points.push_back(p); } ifstream qin("questions-5.txt"); vector<int> questions; int q; while (qin >> q) { questions.push_back(q); } sort(points.begin(), points.end()); ofstream fout("out.txt"); for (int x : questions) { if (contains(points, x)) { fout << "YES\n"; } else { fout << "NO\n"; } } return 0; }
bashg++ -o fast fast.cpp ./fast
Two new things / Hai điều mới
const vector<int>& points— the&means use the original vector, do not copy it. Without it, C++ copies all 100,000 points every timecontainsis called — 100,000 copies of 100,000 points, and your program is as slow asfind_number.cppagain.constmeans the function promises not to change it. You met&before infor (auto& p : data). Dấu & nghĩa là dùng chính vector đó, không sao chép. Thiếu nó, C++ sao chép cả 100.000 điểm mỗi lần gọi contains — 100.000 lần sao chép 100.000 điểm, và chương trình lại chậm như find_number.cpp. const nghĩa là hàm hứa không thay đổi nó. Bạn đã gặp & trong for (auto& p : data)."\n"instead ofendl— both end the line, butendlalso pushes every line into the file right away, which is slow when you write 100,000 lines. Cả hai đều xuống dòng, nhưng endl còn đẩy từng dòng vào tệp ngay lập tức — chậm khi bạn ghi 100.000 dòng.
Build one piece, then test it / Làm từng phần rồi kiểm tra
Run it on the small files first: out.txt must be the same YES NO YES NO YES as in Section 1. Then the 20,000 files. Then the 100,000 files that took so long in Section 2 — they now finish in under a second. Chạy với tệp nhỏ trước: out.txt phải giống YES NO YES NO YES ở Phần 1. Rồi đến tệp 20.000. Rồi đến tệp 100.000 từng chạy rất lâu ở Phần 2 — giờ chạy xong trong chưa đến một giây.
How many looks does one question take? Halve 100,000 until only 1 is left, counting each halving: Một câu hỏi cần bao nhiêu lần xem? Chia đôi 100.000 cho tới khi chỉ còn 1, đếm từng lần chia đôi:
17 halvings: at most 17 looks per question instead of 100,000. 17 lần chia đôi: nhiều nhất 17 lần xem cho mỗi câu hỏi, thay vì 100.000.
📊 Section 8 — What the Numbers Mean
The steps for all questions, the slow way and the binary search way: Số bước cho mọi câu hỏi, cách chậm và cách tìm kiếm nhị phân:
- 20,000 × 20,000 — slow: 400,000,000. Binary search: 20,000 × 15 = about 300,000. Chậm: 400.000.000. Nhị phân: khoảng 300.000.
- 100,000 × 100,000 — slow: 10,000,000,000. Binary search: 100,000 × 17 = about 1,700,000. Chậm: 10.000.000.000. Nhị phân: khoảng 1.700.000.
Sorting the points once costs almost nothing next to that. The trick was never a faster computer — it was asking fewer questions. Sắp xếp điểm một lần gần như không tốn gì so với con số đó. Bí quyết không phải máy tính nhanh hơn — mà là hỏi ít câu hơn.
🏅 Section 9 — New Requirement: How Many Scored Below Me?
Contestants now ask a different question: how many contestants scored less than x? That number tells each contestant how many people they beat. Write it into out.txt for each question. Thí sinh giờ hỏi câu khác: có bao nhiêu thí sinh được ít hơn x điểm? Con số đó cho mỗi thí sinh biết mình hơn bao nhiêu người. Ghi nó vào out.txt cho mỗi câu hỏi.
First, the idea — watch how a sorted list answers this question: Trước hết là ý tưởng — xem một list đã sắp xếp trả lời câu hỏi này thế nào:
rank-points.txt, sorted. How many contestants scored less than 600? 100 điểm trong rank-points.txt đã sắp xếp. Có bao nhiêu thí sinh được ít hơn 600 điểm?Download the data / Tải tệp dữ liệu
rank-points.txt — the 100 points from the animation, in file order (not sorted). rank-questions.txt — 5 questions: 600 435 470 810 250. 100 điểm trong hình động, theo thứ tự trong tệp (chưa sắp xếp). 5 câu hỏi.
Try it first / Hãy thử trước
Change your contains into a function that answers the new question, and try it on these files. Do not read on until you have tried. Sửa hàm contains thành hàm trả lời câu hỏi mới, rồi thử với các tệp này. Đừng đọc tiếp khi chưa thử.
Your out.txt should be exactly this: Tệp out.txt của bạn phải đúng như sau:
62
38
46
83
16Here is a way that works. It is the same loop as contains, with one part taken out: Đây là một cách làm đúng. Vẫn là vòng lặp của contains, bỏ đi một phần:
cppint countBelow(const vector<int>& points, int x) { int lo = 0; int hi = points.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (points[mid] < x) { lo = mid + 1; } else { hi = mid - 1; } } return lo; }
- It never stops early, not even when
points[mid]isx. Nó không bao giờ dừng sớm, kể cả khi points[mid] bằng x. - When the middle is
xor bigger, it keeps moving left (hi = mid - 1) — looking for the first point that is not belowx. Khi ở giữa bằng x hoặc lớn hơn, nó tiếp tục dời sang trái — để tìm điểm đầu tiên không nhỏ hơn x. - When the loop ends,
losits on that first point. Every point left of it is belowx— solois the count. Khi vòng lặp dừng, lo nằm đúng ở điểm đó. Mọi điểm bên trái nó đều nhỏ hơn x — nên lo chính là số cần đếm.
The whole program, in a new file below.cpp: Toàn bộ chương trình, trong tệp mới below.cpp:
cpp#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int countBelow(const vector<int>& points, int x) { int lo = 0; int hi = points.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (points[mid] < x) { lo = mid + 1; } else { hi = mid - 1; } } return lo; } int main() { ifstream fin("rank-points.txt"); vector<int> points; int p; while (fin >> p) { points.push_back(p); } ifstream qin("rank-questions.txt"); vector<int> questions; int q; while (qin >> q) { questions.push_back(q); } sort(points.begin(), points.end()); ofstream fout("out.txt"); for (int x : questions) { fout << countBelow(points, x) << "\n"; } return 0; }
bashg++ -o below below.cpp ./below
✏️ Section 10 — Exercises
Every exercise has its own two files: the points and the questions. Write each answer into out.txt, one line per question. Like in a contest, every program must finish in under a second. Mỗi bài tập có hai tệp riêng: điểm và câu hỏi. Ghi mỗi đáp án vào out.txt, mỗi câu hỏi một dòng. Giống như khi thi, mỗi chương trình phải chạy xong trong chưa đến một giây.
- For each question
x, how many contestants scoredxor more? Với mỗi câu hỏi x, có bao nhiêu thí sinh được từ x điểm trở lên? ex1-points.txt ex1-questions.txt - For each question
x, how many contestants scored exactlyx? Với mỗi câu hỏi x, có bao nhiêu thí sinh được đúng x điểm? ex2-points.txt ex2-questions.txt - Each question line has two numbers,
a b. How many contestants scored fromatob, both included? Mỗi dòng câu hỏi có hai số a b. Có bao nhiêu thí sinh được từ a đến b điểm, tính cả a và b? ex3-points.txt ex3-questions.txt - For each question
x, what is the lowest score that is at leastx? WriteNONEif there is none. Với mỗi câu hỏi x, điểm thấp nhất mà vẫn từ x trở lên là bao nhiêu? Ghi NONE nếu không có. ex4-points.txt ex4-questions.txt - Every line of the points file is a name and a score, like
Lan 734. For each questionx, write the name of the lowest scorer with at leastxpoints, orNONE. Mỗi dòng của tệp điểm là tên và điểm. Với mỗi câu hỏi x, ghi tên của bạn có điểm thấp nhất mà vẫn từ x trở lên, hoặc NONE. ex5-points.txt ex5-questions.txt - For each question
x, what is the highest score that is belowx? WriteNONEif there is none. Với mỗi câu hỏi x, điểm cao nhất mà vẫn nhỏ hơn x là bao nhiêu? Ghi NONE nếu không có. ex6-points.txt ex6-questions.txt - The computer plays the guessing game: you think of a number from 1 to 1,000 and type
higher,lowerorcorrectafter each guess. It must always find your number in at most 10 guesses. (No data file.) Máy tính chơi trò đoán số: bạn nghĩ một số từ 1 đến 1.000 và gõ higher, lower hoặc correct sau mỗi lần đoán. Máy phải luôn tìm ra số của bạn trong tối đa 10 lần. (Không có tệp dữ liệu.)
Homework
- This points file is already sorted highest first. For each question
x, how many contestants scored more thanx? Do not sort the points again. Tệp điểm này đã được sắp xếp từ cao xuống thấp. Với mỗi câu hỏi x, có bao nhiêu thí sinh được nhiều hơn x điểm? Không được sắp xếp lại. ex8-points.txt ex8-questions.txt