插值搜寻

$$O(\log (\log n))$$

插值搜寻法（Interpolation search）是利用插值公式来计算猜测搜寻键值的位置。搜寻方式与二分搜寻相同。

插值公式：

插值 = (设算数 - 最小数) / (最大数 - 最小数)：

搜寻键值 = left + parseInt( ( key - dataleft ) / ( dataright - dataleft ) )*( right - left ) )

## 算法

插值搜寻之算法与二分搜寻算法几乎完全相同，差别在：

二分搜寻法：猜测键值在中间位置(middle)

插值搜寻法：用插值公式计算键值位置

### 时间复杂度

二分搜寻在一般的情况下时间复杂度是对数时间，进行$O(\log n)$次比较操作（$n$在此处是数组的元素数量，$O$是大O记号，$\log$是对数）。

插值搜寻的最坏时间复杂度是$O(n)$，平均进行$O(\log(\log n))$次比较操作。因为用插值公式计算搜寻键值，能使搜寻范围比二分法更快缩小。所以除非输入数据数量很少，否则插值搜寻比二分搜寻与线性搜寻更快，但数组必须事先被排序。无论对任何大小的输入数据，插值搜寻算法使用的空间复杂度一样是$O(1)$。

### 实作

C code:

```C
#include <stdio.h>

int InterSearch(int A[], int length, int key)
{
    int left = 0, right = length - 1, m;
    while (left <= right && A[left] != A[right]) {
        m = left + ((right - left) * (key - A[left])) / (A[right] - A[left]);
        if (m < left || m > right)
            break;
        if (key < A[m])
            right = m - 1;
        else if (key > A[m])
            left = m + 1;
        else
            return m;
    }
    if (A[left] == key)
        return left;
    return -1;
}

int main()
{
    int A[] = { 1, 3, 16, 31, 43, 354, 586 };
    int length = sizeof(A) / sizeof(A[0]);

    printf("Index of 43: %d\n", InterSearch(A, length, 43));
    printf("Index of 354: %d\n", InterSearch(A, length, 354));
    printf("Index of 3: %d\n", InterSearch(A, length, 3));

    return 0;
}
```

JS code:

```javascript
var interpolationSearch = function(data, key){
    var left = 0;
    var right = data.length - 1;
    var m = 0;
    while(left <= right){
        var m = parseInt((right - left)*(key - data[left])/(data[right] - data[left])) + left;
        if( m < left || m > right)
            break;
        if(key < data[m])
            right = m - 1;
        else if(key > data[m])
            left = m + 1;
        else
            return m;			
    }
    return -1;
};

//執行
var data = getRandomData();
quickSort(data, 0, data.length-1);
interpolationSearch(data, 5);        // (data, key)
```

### Julia (程式语言)

```julia
# Julia Sample : InterSearch
function InterSearch(A,key)
	left,right,m = 1, length(A), 1
	while(left<=right)
		m=floor(Int,((right-left)*(key-A[left])/(A[right]-A[left])+left))
	
		if (m<left)||(m>right)
			break
		end

		if key<A[m]
			right=m-1
		elseif key>A[m]
			left=m+1
		else
			return m
		end

	end
	return -1
end

# Main Code
A = [1,3,16,31,43,354,586]	 # Already Arrange
println(A)                   # Original Array
println(InterSearch(A,43))   # Interpolation Search Array
println(InterSearch(A,354))  # Interpolation Search Array
println(InterSearch(A,3))    # Interpolation Search Array
```

Python3

```python3
def interpolation_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high and arr[low] <= x <= arr[high]:
        mid = low + ((high - low) // (arr[high] - arr[low])) * (x - arr[low])
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 测试用例
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]
x = 60
result = interpolation_search(arr, x)
print(f"元素在数组中的索引为: {result}")
```

## 基本资料

- 车辆类别：搜索算法
- data：数组
- 时间：$O(n)$
- 容积、占地面积：$O(1)$
- best-time：$O(1)$
- average-time：$O(\log (\log n))$
- optimal：Yes