Tìm nhanh bằng cách chia đôi: tra từ điển, đoán số và cân đồng xu

Tìm kiếm bằng cách chia đôi là nhìn vào chính giữa một danh sách đã xếp thứ tự, rồi bỏ hẳn nửa chắc chắn không chứa thứ mình cần. Mỗi lần nhìn loại được một nửa, nên đoán một số bí mật từ 1 đến 100 chỉ cần nhiều nhất 7 lần, vì 2 nhân với chính nó 7 lần là 128, lớn hơn 100. Người lập trình gọi cách này là tìm kiếm nhị phân, và bạn đã dùng nó mỗi lần tra từ điển giấy.

Tìm lần lượt và tìm chia đôi

Có hai cách cơ bản để tìm một thứ trong danh sách:

• Tìm lần lượt: xem từng thứ một từ đầu tới cuối. Cách này luôn dùng được, kể cả khi danh sách lộn xộn. Nhưng nếu danh sách có một nghìn mục, có khi phải xem cả nghìn.
• Tìm chia đôi: nhìn mục ở giữa, so với thứ cần tìm, bỏ một nửa, lặp lại. Chỉ dùng được khi danh sách đã xếp theo thứ tự, nhưng nhanh hơn rất nhiều.

Hãy hình dung một ngăn tủ hồ sơ của trường có 1.000 tập, xếp theo tên học sinh. Tìm lần lượt, trung bình phải lật khoảng 500 tập. Tìm chia đôi, nhiều nhất 10 lần nhìn là thấy.

Đoán số từ 1 đến 100 trong 7 lần

Một bạn nghĩ thầm một số từ 1 đến 100. Bạn kia đoán, sau mỗi lần đoán được nghe "lớn hơn", "nhỏ hơn" hoặc "đúng rồi". Nhiều người đoán theo cảm tính: 37, rồi 80, rồi 15… Cách chắc chắn nhất là luôn đoán số ở giữa khoảng còn lại.

Giả sử số bí mật là 73:

1. Khoảng 1–100, đoán 50. "Lớn hơn." Còn lại 51–100.
2. Đoán 75. "Nhỏ hơn." Còn lại 51–74.
3. Đoán 62. "Lớn hơn." Còn lại 63–74.
4. Đoán 68. "Lớn hơn." Còn lại 69–74.
5. Đoán 71. "Lớn hơn." Còn lại 72–74.
6. Đoán 73. "Đúng rồi."

Sáu lần. Dù số bí mật là bao nhiêu, cách đoán chính giữa không bao giờ cần quá 7 lần. Lý do nằm ở phép chia đôi liên tiếp: 100 số còn 50, rồi 25, rồi khoảng 13, khoảng 7, khoảng 4, 2, và 1. Bảy lần chia đôi là đủ để khoanh xuống còn một số.

Danh sách dài gấp đôi, chỉ thêm một lần đoán

Điều kỳ diệu của cách chia đôi là danh sách dài thêm rất nhiều mà số lần tìm chỉ tăng một chút. Mỗi lần danh sách dài gấp đôi, chỉ cần thêm đúng một lần nhìn.

Số mục trong danh sách	Tìm lần lượt (nhiều nhất)	Tìm chia đôi (nhiều nhất)
10	10	4
100	100	7
1.000	1.000	10
1.000.000	1.000.000	20
8 tỉ (gần bằng dân số thế giới)	8 tỉ	33

Nếu có một danh sách tên của mọi người trên Trái Đất, xếp theo thứ tự, thì 33 lần nhìn là đủ để tìm bất kỳ ai. Đó là vì 2 nhân với chính nó 33 lần được hơn 8,5 tỉ. Các nhà toán học gọi số lần chia đôi này là lôgarit cơ số 2, một khái niệm bạn sẽ gặp ở lớp trên.

Bạn đã dùng cách chia đôi ở đâu

Tra từ điển giấy

Không ai tra từ "quả" bằng cách lật từ trang đầu tiên. Ta mở đại khoảng giữa quyển, thấy đang ở vần "M", biết "Q" nằm sau nên lật về phía sau, rồi lật tới lui vài lần là tới. Người tra từ điển giỏi còn làm tốt hơn chia đôi đúng kiểu: biết "Q" nằm gần cuối nên mở luôn ở khoảng hai phần ba quyển. Các nhà khoa học máy tính cũng có thuật toán dùng kiểu "đoán chỗ" như vậy khi dữ liệu phân bố đều.

Tìm trang trong sách

Cô giáo bảo mở trang 143 của quyển sách 300 trang. Bạn mở khoảng giữa, thấy trang 160, lật lùi một ít, thấy 138, lật tới vài tờ. Đó chính là tìm chia đôi, chỉ không chia chính xác.

Tìm chỗ bắt đầu sai

Một bài toán dài 16 dòng ra đáp số sai. Thay vì dò lại từ dòng 1, kiểm tra kết quả ở dòng 8. Đúng thì lỗi nằm ở dòng 9 trở đi, sai thì lỗi nằm từ dòng 1 tới 8. Bốn lần kiểm là khoanh tới đúng một dòng. Người lập trình làm đúng như vậy khi một phần mềm đang chạy tốt ở bản cũ mà hỏng ở bản mới: họ thử bản ở giữa, rồi chia đôi tiếp, để tìm ra lần sửa nào đã gây lỗi.

Điều kiện bắt buộc: phải đã xếp thứ tự

Cách chia đôi chỉ chạy khi nhìn vào mục ở giữa, ta biết chắc thứ cần tìm nằm bên trái hay bên phải. Với một chồng bài kiểm tra xếp lộn xộn, nhìn tờ ở giữa chẳng cho biết gì về những tờ còn lại. Vì vậy tìm kiếm chia đôi thường đi đôi với sắp xếp.

Sắp xếp tốn công. Nếu chỉ cần tìm một lần trong một danh sách nhỏ, tìm lần lượt có khi nhanh hơn. Nhưng nếu cùng một danh sách được tìm hàng nghìn lần, như danh bạ, từ điển hay kho sách thư viện, thì bỏ công xếp một lần là rất đáng.

Biến thể: chia ba khi dùng cân hai đĩa

Có một câu đố nổi tiếng: có 9 đồng xu trông giống hệt nhau, một đồng nhẹ hơn một chút. Có một chiếc cân hai đĩa. Cần ít nhất mấy lần cân để tìm ra đồng nhẹ?

Nhiều người nghĩ tới chia đôi, nhưng 9 không chia đôi được gọn. Bí quyết là chia ba, vì mỗi lần cân cho ba kết quả: lệch trái, lệch phải, hoặc thăng bằng.

1. Chia 9 đồng thành ba nhóm, mỗi nhóm 3 đồng. Đặt nhóm A lên đĩa trái, nhóm B lên đĩa phải. Nếu một đĩa nhẹ hơn, đồng xu nhẹ nằm ở nhóm đó. Nếu cân thăng bằng, nó nằm ở nhóm C chưa cân.
2. Lấy 3 đồng của nhóm nghi ngờ. Đặt một đồng lên mỗi đĩa. Đĩa nào nhẹ hơn thì đồng đó là đồng cần tìm. Thăng bằng thì đồng còn lại trong tay là đồng nhẹ.

Chỉ hai lần cân. Bài học: hãy nhìn xem mỗi lần kiểm tra cho bao nhiêu kết quả khác nhau, rồi chia sao cho mỗi kết quả loại được nhiều nhất.

Ba lỗi hay gặp

• Quên điều kiện thứ tự: dùng cách chia đôi trên danh sách chưa xếp, kết quả là bỏ sót mà không biết.
• Đoán không chia đều: hỏi "có phải số 37 không?" ngay lần đầu chỉ loại được một số. Câu hỏi tốt là câu hỏi loại được khoảng một nửa.
• Lệch một ở hai đầu: sau khi nghe "lớn hơn 50", khoảng mới là 51–100 chứ không phải 50–100. Viết nhầm đầu mút là một lỗi kinh điển khi lập trình tìm kiếm chia đôi, đến người nhiều kinh nghiệm cũng vẫn mắc.

Thử làm: ba hoạt động chia đôi

Đoán số và ghi lại số lần

Làm theo cặp. Một bạn nghĩ số từ 1 đến 100, bạn kia đoán theo cách chọn chính giữa và ghi lại mỗi lần đoán. Đổi vai mười lần. Có lần nào cần tới 8 lần không? Sau đó thử khoảng 1 đến 1.000, đoán trước xem cần nhiều nhất bao nhiêu lần.

Tra từ điển có đếm

Một bạn đọc to một từ, bạn kia tra trong từ điển giấy và đếm số lần mở hoặc lật trang. Lần đầu tra theo thói quen, lần sau tra theo đúng kiểu chia đôi. Cách nào ít lần lật hơn?

Cân đồng xu bằng móc áo

Làm một chiếc cân đơn giản: treo một móc áo lên tay nắm cửa, buộc hai cốc giấy giống nhau vào hai đầu bằng dây chỉ dài bằng nhau. Dùng 9 chiếc nắp chai giống nhau, nhờ người lớn dán thêm một mẩu băng dính nhỏ vào mặt trong một chiếc để nó nặng hơn chút. Lần này tìm chiếc nặng hơn bằng đúng hai lần cân, theo cách chia ba ở trên. Nếu cân không đủ nhạy, thay băng dính bằng một đồng xu nhỏ.

Câu hỏi thường gặp

Tìm kiếm nhị phân là gì?

Tìm kiếm nhị phân là cách tìm một mục trong danh sách đã xếp thứ tự bằng cách nhìn vào mục ở giữa, rồi bỏ nửa không chứa thứ cần tìm. Lặp lại với nửa còn lại cho tới khi tìm thấy. Mỗi lần nhìn loại được một nửa danh sách nên tìm rất nhanh.

Vì sao đoán số từ 1 đến 100 chỉ cần 7 lần?

Nếu luôn đoán số chính giữa khoảng còn lại, mỗi lần đoán sai sẽ loại được khoảng một nửa số khả năng. Chia đôi 100 liên tiếp 7 lần là còn một số, vì 2 nhân với chính nó 7 lần được 128, lớn hơn 100. Vì vậy 7 lần là đủ cho mọi trường hợp.

Tìm kiếm nhị phân khác tìm kiếm tuần tự thế nào?

Tìm kiếm tuần tự xem từng mục một từ đầu tới cuối và dùng được với danh sách chưa xếp. Tìm kiếm nhị phân cần danh sách đã xếp thứ tự nhưng nhanh hơn rất nhiều: với một triệu mục, tuần tự có thể phải xem cả triệu, còn nhị phân chỉ cần khoảng 20 lần.

Câu đố 9 đồng xu cân 2 lần giải thế nào?

Chia 9 đồng thành ba nhóm 3 đồng, cân hai nhóm với nhau để biết đồng nhẹ nằm ở nhóm nào. Lấy nhóm đó, đặt một đồng lên mỗi đĩa: đĩa nhẹ hơn là đồng cần tìm, còn thăng bằng thì là đồng còn lại. Mấu chốt là mỗi lần cân cho ba kết quả nên chia ba có lợi hơn chia đôi.