Tìm kiếm nội suy
Khi tìm "Trần" trong danh bạ điện thoại, bạn không mở ở giữa: bạn mở gần cuối, vì T nằm gần cuối bảng chữ cái. Tìm kiếm nội suy làm điều tương tự với các con số. Nó đoán mục tiêu nên nằm ở đâu dựa vào độ lớn của nó, và với dữ liệu phân bố đều, phỏng đoán đó chính xác đáng kinh ngạc.
Ý tưởng
Tìm kiếm nhị phân luôn dò ở giữa, bất kể đang tìm gì. Tìm kiếm nội suy dùng các giá trị. Nếu phần còn lại của danh sách chạy từ 10 đến 100 và mục tiêu là 70, mục tiêu nằm ở hai phần ba quãng từ giá trị đầu đến giá trị cuối, nên nó dò ở hai phần ba chiều dài. Viết thành công thức, vị trí dò là lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Sau khi dò, nó giữ phần ở phía đúng, y như tìm kiếm nhị phân, rồi ước tính lại.
Hai ví dụ
Trong 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, tìm 70 sẽ dò ngay vị trí 7: tìm thấy sau 1 lần dò, trong khi tìm kiếm nhị phân cần 4. Giờ lấy 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 và tìm 9. Vì có 999, mọi ước tính đều rơi gần đầu: quá trình tìm kiếm dò vị trí 1, 2, 3, v.v., mỗi lần một vị trí, và cần 9 lần dò, trong khi tìm kiếm nhị phân cần 3.
Nhanh đến mức nào
Khi các giá trị phân bố đều, hoặc được lấy ngẫu nhiên từ một phân phối đều, mỗi lần dò thu nhỏ phần còn lại từ khoảng n xuống khoảng √n. Nhờ đó trung bình cần khoảng log₂(log₂ n) lần dò: khoảng 5 ngay cả với một tỷ giá trị, so với 30 của tìm kiếm nhị phân. Khi các giá trị phân bố rất không đều, một lần dò có thể chỉ loại được một giá trị, và trường hợp xấu nhất là n lần dò, tệ như tìm kiếm tuyến tính. Mỗi lần dò còn tốn một phép chia, nên trên thực tế nó chủ yếu có lợi khi mỗi lần dò tốn kém, chẳng hạn đọc từ đĩa.
Lịch sử và các biến thể
W. W. Peterson mô tả tìm kiếm nội suy vào năm 1957, để tìm bản ghi trên bộ nhớ truy cập ngẫu nhiên. Mức trung bình log log n với khóa phân bố đều được Perl, Itai và Avni chứng minh vào năm 1978. Các phiên bản thực tế đề phòng dữ liệu xấu bằng cách xen các bước nhị phân, ví dụ tìm kiếm nội suy-tuần tự hoặc tìm kiếm nội suy-nhị phân, để trường hợp xấu nhất vẫn gần log n.
Khám phá
Mở ứng dụng, chọn một giá trị ở ô Tìm và nhấn Bước. Mỗi lần dò cho biết mục tiêu nằm ở đâu giữa hai giá trị đầu mút và điều đó chỉ đến vị trí nào. Chuyển Phân bố sang Đều thì phần lớn các lần tìm kết thúc sau một lần dò; chuyển sang Lệch thì các lần dò bò dần ở đầu danh sách. Ô cuối cùng cho biết tìm kiếm nhị phân cần bao nhiêu bước cho cùng giá trị đó.
Câu hỏi thường gặp
Độ phức tạp thời gian của tìm kiếm nội suy là bao nhiêu?
Trung bình O(log log n) với các giá trị phân bố đều, và O(n) trong trường hợp xấu nhất. Nó cần O(1) bộ nhớ phụ và một danh sách đã sắp xếp.
Tìm kiếm nội suy khác tìm kiếm nhị phân thế nào?
Tìm kiếm nhị phân luôn dò ở giữa phần còn lại. Tìm kiếm nội suy dò ở nơi mục tiêu nên nằm, dựa vào giá trị ở hai đầu. Cách này tốt hơn nhiều với giá trị phân bố đều và có thể tệ hơn nhiều với giá trị lệch.
Loại dữ liệu nào hợp với tìm kiếm nội suy?
Các khóa số đã sắp xếp và phân bố khá đều: ID tuần tự ít khoảng trống, dấu thời gian của các sự kiện đều đặn, hoặc khóa đã băm. Nó hợp với dữ liệu mà mỗi lần dò tốn kém còn một chút tính toán thì rẻ.
Vì sao ứng dụng có nhiều kiểu phân bố?
Vì cách phân bố quyết định ước tính tốt đến đâu. Giá trị đều khiến tìm kiếm nội suy trông gần như kỳ diệu, còn giá trị lệch cho thấy điểm yếu của nó. So sánh chúng với số bước của tìm kiếm nhị phân là cách rõ nhất để biết khi nào dùng cách nào.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử tìm kiếm nội suy