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ố:

This 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ỡ.

  1. In your program, change "points-5.txt" to "points-20000.txt" and "questions-5.txt" to "questions-20000.txt". Save, compile with g++ 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ờ.
  2. Now change both names to the 100k files, 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.

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.

Count the steps / Đếm số bước
734
205
918
512
367
steps = 0
out.txt
The 5 points from 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.
1 / 27

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.

🧩 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.

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.

Guess my number / Đoán số của máy
guesses = 0
I am thinking of a number from 1 to 100. Click a number to guess it. Máy đang nghĩ một số từ 1 đến 100. Bấm vào một số để đoán.

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:

100→ 
50→1
25→2
13→3
7→4
4→5
2→6
17

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.

Always guess the middle / Luôn đoán số ở giữa
guesses = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
The computer picks a number from 1 to 100. Every number is still possible. Máy chọn một số từ 1 đến 100. Số nào cũng có thể.
1 / 10

🔍 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:

Watch binary search / Xem tìm kiếm nhị phân
x = 738
lo
115
130
136
142
160
164
192
196
245
261
289
290
294
347
410
434
505
551
557
562
563
575
576
587
620
624
641
651
673
701
709
714
728
730
738
744
749
765
769
810
856
896
899
912
923
929
951
975
977
hi
986
50 points, sorted. Is 738 one of them? 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.
1 / 27

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.

Binary search in code, line by line / Tìm kiếm nhị phân bằng code, từng dòng một
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;
}
Variables / Biến
x760lo—hi—mid—points[mid]—
105
125
130
155
155
175
175
185
185
200
210
210
215
225
230
235
285
295
305
310
320
325
335
345
345
350
350
355
370
380
390
395
400
400
415
415
430
430
435
445
450
450
455
455
455
465
470
470
470
480
485
490
495
495
510
510
530
535
555
560
575
595
605
610
625
625
640
650
655
660
675
690
700
705
710
745
750
760
765
780
785
800
800
810
830
845
850
865
875
885
900
900
905
910
910
920
925
955
960
995
We ask: is 760 one of the 100 sorted points? That is the call 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.
1 / 27

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; }
bash
g++ -o fast fast.cpp ./fast

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:

100,000→ 
50,000→1
25,000→2
12,500→3
6,250→4
3,125→5
1,563→6
782→7
391→8
196→9
98→10
49→11
25→12
13→13
7→14
4→15
2→16
117

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:

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:

How counting below works / Cách đếm số điểm nhỏ hơn
x = 600
105
125
130
155
155
175
175
185
185
200
210
210
215
225
230
235
285
295
305
310
320
325
335
345
345
350
350
355
370
380
390
395
400
400
415
415
430
430
435
445
450
450
455
455
455
465
470
470
470
480
485
490
495
495
510
510
530
535
555
560
575
595
605
610
625
625
640
650
655
660
675
690
700
705
710
745
750
760
765
780
785
800
800
810
830
845
850
865
875
885
900
900
905
910
910
920
925
955
960
995
The 100 points from 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?
1 / 32

Here 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:

cpp
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; }

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; }
bash
g++ -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.

Homework