Tổng quan
Interpolation Search (tìm kiếm nội suy) cải tiến Binary Search cho dữ liệu đã sắp xếp và phân bố đều. Thay vì luôn dò ở điểm giữa, nó ước lượng vị trí có khả năng chứa mục tiêu dựa trên giá trị của nó so với hai đầu khoảng — giống như đoán trang chứa một cái tên trong danh bạ.
Khi các giá trị trải đều, phép dò dựa trên giá trị này rơi rất gần mục tiêu, nên thuật toán có thể vượt Binary Search. Tuy nhiên, với dữ liệu lệch, các ước lượng trở nên tồi và hiệu năng suy giảm mạnh.
Tìm kiếm nội suy hoạt động thế nào?
- Đặt low và high tại hai biên của mảng đã sắp xếp.
- Ước lượng vị trí dò bằng cách nội suy giá trị của mục tiêu giữa giá trị tại low và high.
- So sánh phần tử tại vị trí dò đó với mục tiêu.
- Nếu mục tiêu lớn hơn, chuyển low ra sau vị trí dò; nếu nhỏ hơn, chuyển high ra trước nó.
- Lặp lại cho đến khi tìm thấy giá trị hoặc khoảng trở nên rỗng.
Khi nào nên dùng?
- Mảng lớn đã sắp xếp gồm các khóa số phân bố đều.
- Tra cứu khi giá trị tăng đều đặn, chẳng hạn ID tuần tự hoặc các phép đo cách đều.
- Tránh dùng với dữ liệu co cụm hoặc lệch, khi các đảm bảo của Binary Search an toàn hơn.
Phân tích độ phức tạp
Trên dữ liệu đã sắp xếp và phân bố đều, Interpolation Search trung bình O(log log n) — nhanh hơn Binary Search — vì mỗi phép dò thu hẹp khoảng rất mạnh. Nhưng với dữ liệu lệch hoặc co cụm, các ước lượng không đáng tin và nó có thể suy giảm xuống O(n) ở trường hợp xấu nhất. Nó dùng O(1) bộ nhớ phụ.
Câu hỏi thường gặp
Interpolation Search khác Binary Search thế nào?
Binary Search luôn dò điểm giữa; Interpolation Search dò tại nơi mà giá trị của mục tiêu gợi ý nó nên ở đó. Phỏng đoán này rất tốt trên dữ liệu đều nhưng không đáng tin khi các giá trị cách nhau không đều.
Khi nào Interpolation Search hoạt động kém?
Trên các phân bố lệch hoặc co cụm, công thức nội suy liên tục đoán xa mục tiêu, nên khoảng thu hẹp chậm và chi phí có thể tiệm cận O(n) của một lần quét tuyến tính.