Giao diện
Thuật toán Tìm kiếm
Mọi hệ thống phần mềm đều xoay quanh một thao tác: tìm. Tìm user trong database, tìm sản phẩm trong catalog, tìm log entry trong hàng triệu dòng — khác biệt giữa O(n) và O(log n) trên 100 triệu bản ghi là khác biệt giữa 3 phút và 0.0003 giây.
Hiểu đúng thuật toán tìm kiếm không chỉ là chuyện "biết dùng cái nào". Đó là khả năng nhận ra khi nào linear scan là tối ưu thực sự, khi nào binary search lại phản tác dụng, và khi nào cần tư duy parametric search để giải những bài toán tưởng chừng không liên quan đến tìm kiếm.
Bảng so sánh tổng quan
| Thuật toán | Time (worst) | Time (avg) | Yêu cầu dữ liệu | Khi nào dùng |
|---|---|---|---|---|
| Linear Search | O(n) | O(n) | Không cần sắp xếp | Mảng nhỏ, dữ liệu chưa sort, streaming |
| Binary Search | O(log n) | O(log n) | Đã sắp xếp | Mảng lớn đã sort, tìm biên, parametric search |
| Interpolation Search | O(n) | O(log log n) | Đã sắp xếp, phân bố đều | Dữ liệu số phân bố uniform (database indexing) |
| Exponential Search | O(log n) | O(log n) | Đã sắp xếp | Mảng không biết kích thước, unbounded search |
Quy tắc ngón tay cái
Nếu n ≤ 64 hoặc dữ liệu chưa sort → Linear Search thường nhanh hơn cả Binary Search do cache locality và overhead thấp. Binary Search chỉ thực sự tỏa sáng khi n lớn và dữ liệu đã sắp xếp sẵn.
Lộ trình học
Bắt đầu từ Linear Search — không phải vì nó dễ, mà vì nó dạy bạn tư duy sequential scan và cache-friendly access. Sau đó chuyển sang Binary Search, thuật toán xuất hiện nhiều nhất trong phỏng vấn và có nhiều biến thể tinh tế hơn bạn nghĩ.
Thứ tự khuyến nghị:
- Linear Search — nền tảng, sentinel optimization, khi nào linear là tối ưu
- Binary Search — iterative vs recursive, lower/upper bound, parametric search, off-by-one pitfalls
Nội dung
Tìm kiếm tuần tự (Sequential)
- Linear Search — Tìm kiếm tuyến tính — Thuật toán nền tảng, tối ưu sentinel, phân tích cache locality
Tìm kiếm theo khoảng (Interval)
- Binary Search — Tìm kiếm nhị phân — Iterative/recursive, lower_bound/upper_bound, parametric search, xử lý off-by-one
🧠 Quiz
Câu 1: Binary Search có thể áp dụng ngoài mảng sắp xếp không?
- [ ] A) Không, chỉ dùng cho mảng sắp xếp
- [x] B) Có — Binary Search on Answer áp dụng khi hàm mục tiêu có tính đơn điệu (monotonic)
- [ ] C) Có, nhưng chỉ cho linked list
- [ ] D) Không, vì cần random access
💡 Giải thích: "Binary Search on Answer" là kỹ thuật mạnh: thay vì tìm phần tử trong mảng, ta binary search trên không gian đáp án. Ví dụ: "tốc độ tối thiểu để hoàn thành trong T giờ?" — nếu v đủ thì v+1 cũng đủ (monotonic) → binary search được.
Câu 2: Độ phức tạp O(log n) của Binary Search nghĩa là gì thực tế?
- [ ] A) Cần log₁₀(n) bước
- [x] B) Mỗi bước loại bỏ nửa không gian tìm kiếm → với 1 tỷ phần tử chỉ cần ~30 bước
- [ ] C) Chạy chậm hơn O(n) một chút
- [ ] D) Cần n × log(n) phép so sánh
💡 Giải thích: log₂(10⁹) ≈ 30. Nghĩa là trong mảng 1 tỷ phần tử, Binary Search tìm được kết quả sau tối đa 30 lần so sánh. Mỗi bước chia đôi: 10⁹ → 5×10⁸ → 2.5×10⁸ → ... → 1.