Tìm kiếm bằng ngón tay trên cấu trúc dữ liệu được định nghĩa là phần mở rộng của bất kỳ thao tác tìm kiếm nào mà cấu trúc hỗ trợ, trong đó tham chiếu (ngón tay) đến một phần tử trong cấu trúc dữ liệu được đưa ra cùng với truy vấn. Mặc dù thời gian tìm kiếm phần tử thường được biểu thị dưới dạng hàm của số phần tử trong cấu trúc dữ liệu, nhưng thời gian tìm kiếm bằng ngón tay được coi là hàm của khoảng cách giữa phần tử và ngón tay.
Trong một tập hợp có m phần tử, khoảng cách d (a, b) giữa hai phần tử a và b là hiệu số bậc của chúng. Nếu phần tử a và b là phần tử lớn nhất thứ i và thứ j trong cấu trúc, thì sự khác biệt về thứ hạng là | i - j |. Nếu một tìm kiếm thông thường trong một cấu trúc nào đó thường tiêu tốn thời gian O (f (m)), thì một tìm kiếm ngón tay cho phần tử a với phần tử b một cách lý tưởng sẽ tiêu tốn thời gian O (f (d)). Lưu ý rằng vì d ≤ m, nên trong trường hợp xấu nhất, tìm kiếm bằng ngón tay chỉ kém như tìm kiếm thông thường. Tuy nhiên, trên thực tế các tìm kiếm ngón tay thoái hóa này thực hiện nhiều công việc hơn các tìm kiếm bình thường. Ví dụ, nếu f (n) là log (n) và tìm kiếm theo ngón tay thực hiện nhiều so sánh gấp đôi so với tìm kiếm thông thường trong trường hợp xấu nhất, thì tìm kiếm theo ngón tay sẽ chậm hơn khi d> √n. Do đó, tìm kiếm bằng ngón tay chỉ nên được triển khai khi người ta có thể mong đợi một cách hợp lý mục tiêu thực sự ở gần ngón tay.
Triển khai
Một số cấu trúc dữ liệu phổ biến hỗ trợ tìm kiếm bằng ngón tay mà không cần thay đổi thêm cấu trúc thực tế. Trong các cấu trúc mà việc tìm kiếm phần tử a được thực hiện bằng cách thu hẹp khoảng thời gian có thể tìm thấy a, tìm kiếm ngón tay từ phần tử b thường được thực hiện bằng cách đảo ngược quá trình tìm kiếm từ b cho đến khi khoảng tìm kiếm đủ lớn để chứa phần tử a, tại tìm kiếm điểm nào diễn ra bình thường.
Danh sách liên kết được sắp xếp
Trong danh sách được liên kết, người ta thường tìm kiếm một phần tử theo cách tuyến tính bằng cách đi ngang từ đầu này sang đầu kia. Nếu danh sách liên kết được sắp xếp và chúng tôi có tham chiếu đến một số nút chứa phần tử b, thì chúng tôi có thể tìm thấy phần tử a trong thời gian O (d) bằng cách bắt đầu tìm kiếm của chúng tôi từ phần tử b.
Mảng được sắp xếp
Trong một mảng B đã sắp xếp, người ta thường tìm kiếm một phần tử a trong B bằng tìm kiếm nhị phân. Tìm kiếm bằng ngón tay được thực hiện bằng cách triển khai tìm kiếm một phía từ B [j] =b. Trong khi tìm kiếm nhị phân giảm một nửa không gian tìm kiếm sau mỗi lần so sánh, tìm kiếm một phía sẽ tăng gấp đôi không gian tìm kiếm sau mỗi lần so sánh. Cụ thể, ở lần lặp thứ k của tìm kiếm một phía (giả sử a> b), khoảng đang xét là B [j, j + 2 k-1 ]. Việc mở rộng sẽ tạm dừng ngay sau khi B [j + 2 k-1 ] ≥ a, tại thời điểm này khoảng này được tìm kiếm nhị phân cho phần tử a. Nếu tìm kiếm một phía sử dụng k lần lặp để tìm một khoảng có chứa phần tử a, thì nó tuân theo d> 2 k-2 . Tìm kiếm nhị phân phạm vi này cũng sẽ sử dụng k lần lặp khác. Do đó, ngón tay tìm kiếm a từ b tiêu tốn thời gian O (k) =O (log d)
.
Bỏ qua danh sách
Trong danh sách bỏ qua, người ta có thể tìm kiếm phần tử a từ một nút chứa phần tử b bằng cách tiếp tục tìm kiếm từ điểm này. Lưu ý rằng nếu a
Treaps
Treap được định nghĩa là cây tìm kiếm nhị phân ngẫu nhiên (BST). Tìm kiếm trong một treap tương tự như tìm kiếm một phần tử trong bất kỳ BST nào khác. Tuy nhiên, treap có đặc tính là độ dài đường dẫn dự kiến giữa hai phần tử của xa được ký hiệu là O (log d). Do đó, để tìm kiếm ngón tay từ nút chứa phần tử b cho phần tử a, người ta có thể leo lên cây từ phần tử b cho đến khi tìm thấy tổ tiên của phần tử a, lúc đó tìm kiếm BST bình thường vẫn tiến hành như bình thường. Mặc dù việc tính toán xem một nút có phải là tổ tiên của nút khác hay không, nhưng người ta có thể tăng cường cây để hỗ trợ các truy vấn dạng này để cung cấp thời gian tìm kiếm ngón tay O (log d) dự kiến.
Dây và cây
Việc triển khai dây (cấu trúc dữ liệu) thường sử dụng một trình lặp vị trí dây để truy cập vào dây. Trình lặp có thể được coi là một ngón tay trỏ vào một số ký tự cụ thể của chuỗi. Giống như hầu hết các cây cân bằng, dây thừng yêu cầu thời gian O (log (m)) để truy xuất dữ liệu trong một lá của cây khi chỉ cung cấp gốc của cây. Việc đọc từng chiếc lá của cây dường như cần thời gian O (m * log (m)). Tuy nhiên, bằng cách lưu trữ một ít thông tin bổ sung, trình lặp có thể được triển khai để đọc "lá tiếp theo" chỉ trong thời gian O (1) và mọi lá của cây chỉ trong thời gian O (m).