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.py and run it: Lưu với tên find_number.py rồi chạy:
bashpython find_number.py
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 5,000 contestants send 5,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 5.000 thí sinh gửi 5.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-5000.txt and questions-5000.txt — 5,000 contestants, 5,000 questions. 5.000 thí sinh, 5.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-5000.txt"and"questions-5.txt"to"questions-5000.txt". Save and runpython find_number.py. It finishes — but you have to wait. Trong chương trình, đổi tên hai tệp thành bản 5000. Lưu rồi chạy. Chương trình chạy xong — nhưng bạn phải chờ. - Now change both names to the
100kfiles and run it again. Wait. It does not finish. Giờ đổi cả hai tên sang tệp 100k rồi chạy lại. Chờ. Chương trình không chạy xong.
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 would give 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ó sẽ 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 steps = 0 at the top, 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 steps = 0 ở đầu, 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.
pythonsteps = 0 points = [] with open("points-5.txt") as f: for line in f: points.append(int(line)) questions = [] with open("questions-5.txt") as f: for line in f: questions.append(int(line)) with open("out.txt", "w") as f: for x in questions: found = False for p in points: steps = steps + 1 if p == x: found = True if found: f.write("YES\n") else: f.write("NO\n") print(steps)
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 5,000 files, then work out the 100,000 case — do not run that one: Giờ chạy với tệp 5.000, rồi tính trường hợp 100.000 — đừng chạy trường hợp đó:
- 5 × 5 = 25 steps. 25 bước.
- 5,000 × 5,000 = 25,000,000 steps — the few seconds you waited. 25.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: Python does about 10 million simple steps per second. So 25,000,000 steps take about 2–3 seconds — what you saw. And 10,000,000,000 steps take about 1,000 seconds, around 17 minutes. The program is right, but it is 1,000 times too slow. Quy tắc dễ nhớ: Python làm khoảng 10 triệu bước đơn giản mỗi giây. Vậy 25.000.000 bước mất khoảng 2–3 giây — đúng như bạn thấy. Còn 10.000.000.000 bước mất khoảng 1.000 giây, gần 17 phút. Chương trình đúng, nhưng chậm gấp 1.000 lần.
🧩 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 list: Trò chơi đoán số, viết thành một hàm. Nó làm việc trên một list đã 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.//divides and drops what is after the decimal point:7 // 2is3. mid là lần đoán — vị trí ở giữa. // chia rồi 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 list.
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.py, and keep find_number.py. 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.py, và giữ lại find_number.py.
pythondef contains(points, x): lo = 0 hi = len(points) - 1 while lo <= hi: mid = (lo + hi) // 2 if points[mid] == x: return True if points[mid] < x: lo = mid + 1 else: hi = mid - 1 return False points = [] with open("points-5.txt") as f: for line in f: points.append(int(line)) questions = [] with open("questions-5.txt") as f: for line in f: questions.append(int(line)) points.sort() with open("out.txt", "w") as f: for x in questions: if contains(points, x): f.write("YES\n") else: f.write("NO\n")
bashpython fast.py
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 5,000 files. Then the 100,000 files that got stuck 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 5.000. Rồi đến tệp 100.000 từng bị treo ở 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:
- 5,000 × 5,000 — slow: 25,000,000. Binary search: 5,000 × 13 = about 65,000. Chậm: 25.000.000. Nhị phân: khoảng 65.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:
pythondef count_below(points, x): lo = 0 hi = len(points) - 1 while lo <= hi: 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.py: Toàn bộ chương trình, trong tệp mới below.py:
pythondef count_below(points, x): lo = 0 hi = len(points) - 1 while lo <= hi: mid = (lo + hi) // 2 if points[mid] < x: lo = mid + 1 else: hi = mid - 1 return lo points = [] with open("rank-points.txt") as f: for line in f: points.append(int(line)) questions = [] with open("rank-questions.txt") as f: for line in f: questions.append(int(line)) points.sort() with open("out.txt", "w") as f: for x in questions: f.write(str(count_below(points, x)) + "\n")
bashpython below.py
✏️ 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