Finger Search คืออะไร?
Finger Search = Extension ของ Search Operation: ให้ Reference (Finger) ไปยัง Element ใน Data Structure พร้อมกับ Query
Normal Search Time = f(m) (m = Elements ใน Structure)
Finger Search Time = f(d) (d = Distance ระหว่าง Element และ Finger)
d = |Rank(a) - Rank(b)| ใน Set ของ m Elements
Since d ≤ m → Worst-case Finger Search = Normal Search
But Degenerate Finger Searches ทำงานมากกว่า Normal (เช่น f(n)=log n, Finger Search 2× Comparisons → ช้ากว่าเมื่อ d > √n)
→ Finger Search ควรใช้ตอน Expect Target ใกล้ Finger จริงๆ
Implementations ในโครงสร้างยอดนิยม
1. Sorted Linked Lists
Normal: Linear Traversal O(m)
Finger Search จาก b: เริ่มที่ b → O(d) Time
2. Sorted Arrays
Normal: Binary Search O(log m)
Finger Search: One-Sided Search จาก b
Binary Search: Halve Search Space
One-Sided Search: Double Search Space (Interval: B[j, j+2k-1])
Stop เมื่อ B[j + 2k-1] ≥ a → Binary Search ใน Interval นั้น
k Iterations → d > 2k-2 → Binary Search อีก k → Total O(k) = O(log d)
3. Skip Lists
Continue Search จาก Finger Node b
Backward = Symmetric, Forward = ซับซ้อน (Finger Height 1 → Climb)
แต่ Achieve O(log d) Expected Time
4. Treaps
Randomized BST, Expected Path Length ระหว่าง Elements ระยะ d = O(log d)
Climb จาก b หา Ancestor ของ a → Normal BST Search
Augment สำหรับ Ancestor Queries → Expected O(log d)
5. Ropes (Heavy Strings)
Iterator = Finger ชี้ Character
Normal: O(log m) ต่อ Leaf
With Extra Info: Next Leaf = O(1), All Leaves = O(m)
สรุป
Finger Search = Powerful Technique เมื่อ Access Pattern มี Locality
หลาย Structure รองรับโดยไม่ต้องแก้ Core (Lists, Arrays, Skip Lists, Treaps, Ropes)
Key: Reverse Search จาก Finger จน Interval ครอบคลุม Target → Normal Search
