Tìm kiếm ngón (finger search) trên một cấu trúc dữ liệu được định nghĩa là mở rộng của bất kỳ thao tác tìm kiếm nào mà cấu trúc hỗ trợ, nơi một tham chiếu (ngón/finger) đến một phần tử trong cấu trúc dữ liệu được đưa ra cùng với truy vấn. Trong khi thời gian tìm kiếm một phần tử thường được biểu diễn như hàm của số phần tử trong cấu trúc dữ liệu, thời gian tìm kiếm ngón được coi như hàm của khoảng cách giữa phần tử và ngón.
Trong tập m phần tử, khoảng cách d(a, b) giữa hai phần tử a và b là sự khác biệt về hạng (rank). Nếu a và b là phần tử lớn thứ i và thứ j, thì khác biệt hạng là |i - j|. Nếu tìm kiếm bình thường trong cấu trúc nào đó tốn O(f(m)) thời gian, thì tìm kiếm ngón cho phần tử a với ngón phần tử b lý tưởng nên tốn O(f(d)) thời gian. Chú ý vì d ≤ m, nên trường hợp xấu tìm kiếm ngón chỉ tệ như tìm kiếm bình thường. Tuy nhiên, thực tế các tìm kiếm ngón suy biến (degenerate) làm nhiều việc hơn tìm kiếm bình thường. Ví dụ, nếu f(n) = log(n), và tìm kiếm ngón làm gấp đôi so sánh so với tìm kiếm bình thường trong trường hợp xấu, thì tìm kiếm ngón chậm hơn khi d > √n. Do đó, tìm kiếm ngón chỉ nên dùng khi có thể kỳ vọng hợp lý mục tiêu thực sự gần ngón.
Cài đặt (Implementations)
Một số cấu trúc dữ liệu phổ biến hỗ trợ tìm kiếm ngón mà không cần thay đổi thêm cấu trúc thực tế. Trong các cấu trúc tìm kiếm phần tử a bằng cách thu hẹp khoảng (interval) mà a có thể tìm thấy, tìm kiếm ngón từ phần tử b thường 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 a, lúc đó tìm kiếm tiếp tục như bình thường.
Danh sách liên kết đã sắp xếp (Sorted linked lists)
Trong danh sách liên kết, thường tìm kiếm tuyến tính cho phần tử bằng cách duyệt từ đầu đến cuối. Nếu danh sách liên kết đã sắp xếp, và ta có tham chiếu đến nút chứa phần tử b, thì có thể tìm a trong O(d) thời gian bằng cách bắt đầu tìm kiếm từ b.
Mảng đã sắp xếp (Sorted arrays)
Trong mảng đã sắp xếp B, thường tìm kiếm phần tử a trong B bằng tìm kiếm nhị phân (binary search). Tìm kiếm ngón thực hiện bằng tìm kiếm một chiều (one-sided search) từ B[j] = b. Trong khi tìm kiếm nhị phân chia đôi không gian tìm kiếm sau mỗi so sánh, tìm kiếm một chiều gấp đôi không gian tìm kiếm sau mỗi so sánh. Cụ thể, ở lần lặp thứ k của tìm kiếm một chiều (giả sử a > b), khoảng xét là B[j, j+2k-1]. Mở rộng dừng ngay khi B[j + 2k-1] ≥ a, lúc đó khoảng này được tìm kiếm nhị phân cho a. Nếu tìm kiếm một chiều tốn k lần lặp để tìm khoảng chứa a, thì d > 2k-2. Tìm kiếm nhị phân khoảng này cũng tốn k lần lặp nữa. Do đó, tìm kiếm ngón a từ b tốn O(k) = O(log d) thời gian.
Danh sách bỏ qua (Skip lists)
Trong skip list, có thể finger search phần tử a từ nút chứa phần tử b bằng cách tiếp tục tìm kiếm từ điểm đó. Lưu ý nếu a < b, tìm kiếm hướng lùi, nếu a > b, tìm kiếm hướng tiến. Trường hợp lùi đối xứng với tìm kiếm thông thường, nhưng trường hợp tiến phức tạp hơn. Thông thường tìm kiếm nhanh vì sentinel ở đầu được coi là nút cao nhất. Tuy nhiên, ngón có thể là nút chiều cao 1. Do đó, đôi khi phải leo khi tìm kiếm; điều không xảy ra bình thường. Tuy nhiên, даже với phức tạp này, vẫn đạt O(log d) thời gian tìm kiếm kỳ vọng.
Treaps
Treap được định nghĩa là cây tìm kiếm nhị phân ngẫu nhiên (randomized BST). Tìm kiếm trong treap giống như tìm kiếm trong bất kỳ BST nào. Treaps có tính chất: độ dài đường đi kỳ vọng giữa hai phần tử cách nhau d là O(log d). Do đó, để finger search từ nút chứa b cho a, có thể leo cây từ b cho đến khi tìm thấy tổ tiên của a, lúc đó tìm kiếm BST bình thường tiếp tục. Việc kiểm tra nút có phải tổ tiên không tầm thường, có thể bổ sung cây để hỗ trợ truy vấn dạng này đạt O(log d) finger search kỳ vọng.
Ropes và cây (Ropes and trees)
Các cài đặt của rope (cấu trúc dữ liệu) thường dùng bộ lặp vị trí dây (cord position iterator) để duyệt chuỗi. Bộ lặp có thể coi là ngón trỏ đến ký tự cụ thể của chuỗi. Giống hầu hết cây cân bằng, rope yêu cầu O(log m) thời gian truy xuất dữ liệu ở một lá khi chỉ cho gốc cây. Đọc mọi lá sẽ dường như tốn O(m log m) thời gian. Tuy nhiên, bằng cách lưu thêm chút thông tin, bộ lặp có thể đọc "lá tiếp theo" chỉ trong O(1) thời gian, và đọc mọi lá của cây chỉ trong O(m) thời gian.