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

      
        // Code from https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm
      
        Procedure binary_search
      
           A ← sorted array
      
           n ← size of array
      
           x ← value to be searched
      
           Set lowerBound = 1
      
           Set upperBound = n 
      
           while x not found
      
              if upperBound < lowerBound 
      
                 EXIT: x does not exists.
      
              set midPoint = ( lowerBound +  upperBound  ) / 2
      
              if A[midPoint] < x
      
                 set lowerBound = midPoint + 1
      
              if A[midPoint] > x
      
                 set upperBound = midPoint - 1 
      
              if A[midPoint] = x 
      
                 EXIT: x found at location midPoint
      
           end while
      
        end procedure

view raw Binary Search Demo hosted with ❤ by GitHub

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?

binary search

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?" -

giải thuật binary search 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/17358806/fixing-binary-search-bug-from-bentleys-book-programming-pearls-writing-correc

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

Tag: giai thuat binary search

Chuyện về midpoint trong Binary Search và....bug