by @ToanBui

Mình thường thấy các bạn luôn sử dụng việc tìm kiếm tuyến tính (Linear Search) như một thói quen cho tất cả các trường hợp, nhưng việc này chỉ đúng khi tìm trong một mảng không được sắp xếp.

Ví dụ rằng khi có một list sản phẩm, thường lúc này các sản phẩm sẽ được sắp xếp theo ID khi được trả ra, vậy nên khi tìm các sản phẩm trong list sử dụng Binary Search code của các bạn sẽ được tối ưu đáng kể từ O(n) xuống còn O(logn).

Để mình đưa ra một ví dụ minh họa dễ tưởng tượng hơn. Một quyển sách có 100 trang và mình muốn mở trang sách số 51. Một chiến lược để mở trang mình cần tìm nhanh hơn là mở đến giữa cuốn sách, nếu số trang đang mở cao hơn thì mình lật tiếp trên và nếu nhỏ hơn thì ngược lại, mình lật tiếp nửa dưới.

Như ảnh bên trên, chỉ với 6 lần lặp mình đã có thể tìm được giá trị mong muốn, ở đây là trang sách mình có thể ánh xạ sang với một mảng có 100 phần tử và mỗi trang sách sẽ lưu giữ giá trị là nội dung trang sách, điều này tương đương với giá trị tại vị trí của mảng đó.

Tìm kiếm nhị phân (Binary Search) có thể được sử dụng khá nhiều trong công việc hàng ngày của lập trình viên, một ví dụ đơn giản như khi bạn muốn tìm một item trong giỏ hàng để xóa khi biết với ID item đó sắp xếp tăng dần.

Việc học thêm một đến hai thuật toán chưa chắc sẽ giúp ích gì nhiều trong công việc của các lập trình viên, nhưng nó đem lại một tư tưởng mới, một góc nhìn mới về các vấn đề trong thế giới lập trình, đôi khi nó đem lại một phản xạ tìm nhiều hơn cách giải quyết mới khi gặp một vấn đề.

✏️ System Design VN: https://fb.com/groups/systemdesign.vn
📚 Đọc thêm tài liệu khác: https://roninhub.com/tai-lieu
🎬 Youtube: https://youtube.com/@ronin-engineer