# Finger Search

# Finger Search

Finger search exploits locality. Instead of searching from the root or beginning, it starts from a known position called a finger and moves toward the target. The cost depends on the distance between the finger and the target, not the total size of the structure.

This method appears in ordered data structures such as balanced trees, skip lists, and sorted arrays with auxiliary links.

## Problem

Given an ordered sequence or structure $A$ and a finger position $f$, find an index $i$ such that

$$
A[i] = x
$$

Assume $f$ is close to $i$.

## Idea

Let $d = |i - f|$ be the distance between the finger and the target. Finger search aims to run in

$$
O(\log d)
$$

instead of $O(\log n)$.

The algorithm navigates locally from the finger, often moving up the structure to find a suitable ancestor, then descending toward the target.

## Algorithm (BST Variant)

In a balanced binary search tree, maintain parent pointers.

```id="fs01"
finger_search(node f, x):
    u = f

    while u != null:
        if u.key == x:
            return u

        if x < u.key:
            if u.left != null:
                u = u.left
            else:
                u = u.parent
        else:
            if u.right != null:
                u = u.right
            else:
                u = u.parent

    return null
```

In practice, the algorithm first climbs up until it finds a subtree that could contain $x$, then performs a standard search downward.

## Example

Consider a sorted array:

$$
A = [2, 5, 8, 12, 16, 20, 25, 30]
$$

Finger at index $f = 3$ (value $12$), target $x = 20$.

Distance:

$$
d = |5 - 3| = 2
$$

Search proceeds locally:

| step | index | value | action     |
| ---- | ----- | ----- | ---------- |
| 1    | 3     | 12    | move right |
| 2    | 4     | 16    | move right |
| 3    | 5     | 20    | found      |

The cost depends on $d$, not $n$.

## Correctness

Because the structure is ordered, local comparisons preserve correctness. Moving upward ensures that no possible subtree containing $x$ is skipped. The descent phase mirrors standard search, restricted to a smaller region.

## Complexity

| structure        | time        |
| ---------------- | ----------- |
| balanced BST     | $O(\log d)$ |
| skip list        | $O(\log d)$ |
| array with links | $O(d)$      |

Space:

$$
O(1)
$$

## When to Use

Finger search is effective when:

* successive queries are close in value
* data access exhibits locality
* the structure supports navigation from arbitrary nodes

It is common in editors, sequence data structures, and streaming order statistics.

## Implementation (Array, simple form)

```id="fs02"
def finger_search_array(a, f, x):
    n = len(a)
    i = f

    if a[i] == x:
        return i

    if a[i] < x:
        i += 1
        while i < n and a[i] <= x:
            if a[i] == x:
                return i
            i += 1
    else:
        i -= 1
        while i >= 0 and a[i] >= x:
            if a[i] == x:
                return i
            i -= 1

    return -1
```

```id="fs03"
func FingerSearchArray(a []int, f int, x int) int {
    n := len(a)
    i := f

    if a[i] == x {
        return i
    }

    if a[i] < x {
        for i = i + 1; i < n && a[i] <= x; i++ {
            if a[i] == x {
                return i
            }
        }
    } else {
        for i = i - 1; i >= 0 && a[i] >= x; i-- {
            if a[i] == x {
                return i
            }
        }
    }

    return -1
}
```