# Interpolataion Search內插搜尋
###### tags: `Algorithm` `Datastruction`
先了解會用到的數學斜率計算公式：
資料已經按照順序排列，而內差搜尋法使用線性近似的方式，雖然一開始內插值可能不會剛好是原始的資料值，但至少可以有效率的接近原始的資料值，並每次都將問題分為左子集及右子集。

python code:

# -*- coding: utf-8 -*-
from __future__ import print_function
import random

def interpolation_search(data,val):
    low=0
    high=49
    print('搜尋處理中......')
    while low<= high and val !=-1:
        mid=low+int((val-data[low])*(high-low)/(data[high]-data[low]))#內插法公式（數學斜率）
        if val==data[mid]:
            return mid
        elif val < data[mid]:#左子集，每次都將問題分成兩半
            print('%d 介於位置 %d[%3d]及中間值 %d[%3d]，找左半邊' \
                  %(val,low+1,data[low],mid+1,data[mid]))
            high=mid-1#要看左子集，將尾端改成mid的左邊
        elif val > data[mid]:#右子集，每次都將問題分成兩半
            print('%d 介於中間值位置 %d[%3d] 及 %d[%3d]，找右半邊' \
                  %(val,mid+1,data[mid],high+1,data[high]))
            low=mid+1#要看右子集，將頭改成mid的右邊
    return -1

val=1
data=[0]*50
for i in range(50):#放入亂數
    data[i]=val
    val=val+random.randint(1,5)#這裡亂數會越來越大，因為是自己加上1~5亂數

while True:
    num=0
    val=int(input('請輸入搜尋鍵值(1-150)，輸入-1結束：'))
    if val==-1:
        break
    num=interpolation_search(data,val)
    if num==-1:
         print('##### 沒有找到[%3d] #####' %val)
    else:
        print('在第 %2d個位置找到 [%3d]' %(num+1,data[num]))
	
print('資料內容：')
for i in range(5):
    for j in range(10):
        print('%3d-%-3d' %(i*10+j+1,data[i*10+j]),end='')
    print()