# 插值搜尋

## 演算法

### 實作

JS code: [5]

```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 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
```

## 参考资料

1. ^ YehYeh. 插補搜尋法(Interpolation Search). [2019-06-11]. （原始内容存档于2020-04-27）.
2. ^ {{插值排序}}
3. ^ {{二分搜尋演算法}}
4. ^ Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in o(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. doi:10.1007/3-540-56939-1_58
5. ^ YehYeh. 插補搜尋法(Interpolation Search). [2019-06-11]. （原始内容存档于2020-04-27）.