Chuyện về midpoint trong Binary Search và....bug
Bài viết phân tích một lỗi tinh vi trong thuật toán Binary Search liên quan đến cách tính điểm giữa (midpoint). Tác giả giải thích nguyên nhân gây ra lỗi tràn dữ liệu khi cộng lowerBound và upperBound, và cách khắc phục bằng công thức midPoint = lowerBound + (upperBound - lowerBound) / 2, đồng thời chia sẻ về lịch sử của lỗi này trong sách Programming Pearls.

Bạn đã tự tin mình hiểu và tính midpoint của Binary Search chuẩn chưa?
Nếu bạn nào quên hoặc chưa biết Binary Search là gì có thể xem đoạn code dưới đây
https://gist.github.com/KhoaVanNguyen/5284ae2c0b9e8d8745c4370f1af5d996
Một câu chuyện có thật là Jon Bentley - tác giả của quyển sách lập trình nổi tiếng Programming Pearls. Sau 20 năm sách xuất bản mới có người tìm ra được bug trong đoạn code này?
Vậy bug ở đâu?
Dựa vào tiêu đề của bài này, bạn đã có thể đoán ra bug nằm ở:
dòng 14
midPoint = lowerBound + ( upperBound - lowerBound ) / 2
Có lẽ một số bạn học Binary Search gần đây, một số thầy giáo đã sửa chỗ này lại nhưng không giải thích tại sao phải là
midPoint = lowerBound + ( upperBound - lowerBound ) / 2
mặc dù giá trị của midPoint vẫn không thay đổi mấy?
Nguyên nhân
Ngắn gọn lỗi này là do tràn dữ liệu. Việc bạn cộng lowerBound và upperBound
lowerBound + upperBound
như thế này có thể tràn dữ liệu. Bởi vì tổng có thể lớn hơn giá trị cho phép của int
là [math] 2^31 -1 [/math]
Mà nếu tràn dữ liệu thì tổng của 2 số này sẽ là số âm. Mà số âm chia 2 thì lại là số âm nên sẽ gây ra bug.
Ngược lại, khi lấy upperBound - lowerBound sẽ tránh được lỗi này.
Mặc dù theo suy nghĩa bình thường thì cả 2 cách midPoint
đều ra một giá trị. Nhưng khi đặt vào ngữ cảnh thuật toán Binary Search ta thấy hậu quả thật gê gớm.
Why?
Vậy tại sao phải mất thời gian lâu như vậy, một đại cao thủ trong võ lâm như Jon Bentley mới phát hiện ra lỗi này?
"Mấy chú nói anh viết sách sai là không đúng. Hồi xưa anh tính midPoint vậy là ổn dồi nha, xài mảng cỡ [math]2^30 [/math] phần tử vẫn đúng nha " - Jon Bentley - tui lược dịch
Đùa vậy thôi, chứ hồi xưa chính tác giả cũng không ngờ đến trường hợp này, đây mới là nguyên văn của tác giả:
"The first binary search was published in 1946; when was the first correct search published?" -
Trang 68 - Programming Pearls
Bài học rút ra
Bug hồi xưa không có không có nghĩa là bây giờ cũng vậy.
Chính mình nhiều lần lên mạng copy paste đoạn code về y chang từng dấu cách mà vẫn không chạy được. Hay gõ y chang code trong sách vẫn bug. Mà nếu khi code chạy được khi test với những input khác nhau vẫn có bug, hay lúc chạy được lúc không.
Bài học đó là chính là ngay cả từng đoạn code nhỏ nhấ t cũng rất khó để viết đúng chuẩn, và đa số code trên thế giới này đều rất là phức tạp và không nhỏ tý nào
Dù có "pro" thế nào, như tác giả quyển Programming Pearls cũng mất vài thập kỉ mới có người tìm ra được bug. Vì thế chúng ta phải cẩn thận, code tới đâu hiểu tới đó. Code chạy được không có nghĩa là không có bug!
Bug không tự sinh ra và mất đi - Chỉ chúng ta không thấy mà thôi - Khoa
Reference
http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search
http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search
http://www.csit.parkland.edu/~mbrandyberry/CS1Java/images/Lesson27/
https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://stackoverflow.com/questions/3038392/do-java-arrays-have-a-maximum-size
Related Posts
Discover more content you might enjoy

Game Theory trong thời đại AI: Khi máy móc tham gia vào "trò chơi"
Bài viết phân tích sự giao thoa giữa lý thuyết trò chơi (Game Theory) và trí tuệ nhân tạo, giải thích cách AI đang thay đổi các nguyên lý cân bằng Nash và chiến lược tối ưu. Tác giả đưa ra các ví dụ thực tế về ứng dụng trong kinh doanh, giao thông và an ninh mạng.

Bài này không phải AI viết
Suy ngẫm chân thành về giá trị của việc viết thủ công trong kỷ nguyên AI. Dù AI có thể tạo nội dung hiệu quả, bài viết này là lời khẳng định về sự kết nối cá nhân và giá trị độc đáo mà con người mang lại cho văn bản của mình.

Dự đoán về Vibe Coding: Cách AI sẽ biến đổi việc tạo ra phần mềm
Bài viết phân tích cách 'vibe coding' - phương pháp lập trình dựa trên mô tả ý định thay vì viết code trực tiếp - sẽ dân chủ hóa việc phát triển phần mềm. Tác giả dự đoán về sự chuyển đổi từ giao diện dòng lệnh sang thiết kế trực quan, sự xuất hiện của phần mềm tự cải thiện, và tác động đến cấu trúc tổ chức công ty cũng như các thị trường ngách chưa được khai thác.

Dùng AI để hỗ trợ đầu tư crypto
Bài viết chia sẻ 7 mẹo thực tế để sử dụng AI (như Claude.ai và ChatGPT) hỗ trợ hiểu rõ whitepaper và tài liệu kỹ thuật của các dự án blockchain. Từ việc yêu cầu tóm tắt đơn giản, giải thích như cho trẻ em, đặt câu hỏi làm rõ, sử dụng ví dụ, tạo tình huống giả định, chuyển đổi thuật ngữ, đến so sánh nhiều nguồn tài liệu - giúp nhà đầu tư đưa ra quyết định đầu tư crypto sáng suốt hơn.

Day 19 - Profitable MVP in 30 Days - Đó là một câu chuyện buồn
Bài viết ngày 19 của thử thách xây dựng MVP có lợi nhuận, tác giả chia sẻ câu chuyện buồn về trải nghiệm làm việc với designer trên Fiverr trong bối cảnh đại dịch COVID-19. Bài viết phản ánh về sự vội vàng trong đánh giá, cảm xúc hối hận, và bài học về sự thấu cảm, kiên nhẫn trong giao tiếp trực tuyến, đặc biệt trong thời điểm khó khăn toàn cầu.

Day 22 - Profitable MVP in 30 Days - Launch checklist
Bài viết ngày 22 của thử thách xây dựng MVP có lợi nhuận, tác giả chia sẻ bảng kiểm tra (checklist) chi tiết trước khi ra mắt sản phẩm ReadingPointer. Bài viết phân loại các mục cần kiểm tra thành nhiều nhóm như kỹ thuật, trang web, nội dung quảng bá, kênh phân phối và phân tích dữ liệu, giúp đảm bảo sản phẩm hoàn thiện và sẵn sàng cho người dùng.