Interpolation Search

## How Interpolation Search Works

Interpolation Search is an improved variant of binary search for uniformly distributed sorted arrays. It estimates the position of the target using interpolation formula.

### Algorithm Steps:
1. Calculate position using: pos = low + ((target - arr[low]) × (high - low)) / (arr[high] - arr[low])
2. If arr[pos] equals target, return pos
3. If arr[pos] < target, search in right half
4. If arr[pos] > target, search in left half
5. Repeat until found or interval is empty

### Key Characteristics:
- **Requires sorted array**: Must be sorted
- **Best for uniform distribution**: O(log log n) for uniformly distributed data
- **Estimates position**: Uses value to guess location
- **Degrades for non-uniform data**: Can be O(n) in worst case