插補(bǔ)查找算法又稱為插值查找，它是二分查找算法的改進(jìn)版。插補(bǔ)查找是按照數(shù)據(jù)的分布，利用公式預(yù)測(cè)鍵值所在的位置，快速縮小鍵值所在序列的范圍，慢慢逼近，直到查找到數(shù)據(jù)為止。它類似于平常查字典的方法。例如，我們?cè)诜值洳橐粋€(gè)發(fā)音以字母B開(kāi)頭的文字時(shí)，不會(huì)使用二分查找法找字典的中間部分，因?yàn)楦鶕?jù)字典的順序可知，發(fā)音以B開(kāi)頭的文字應(yīng)該在字典較前的部分，所以可以從字典前部的某處開(kāi)始查找。插補(bǔ)查找算法的所謂中間位置鍵值索引計(jì)算方式：
middle=low+（target-data[low]）/（data[high]-data[low]）*（high-low）
參數(shù)說(shuō)明：
data：數(shù)據(jù)列表
middle：當(dāng)前需要比對(duì)的數(shù)據(jù)索引
low：最左側(cè)數(shù)據(jù)的索引
high：最右側(cè)數(shù)據(jù)的索引
target：查找的目標(biāo)數(shù)據(jù)
現(xiàn)有150位學(xué)生（編號(hào)從1到150）參加軍訓(xùn)拉練，從中隨機(jī)選取9位同學(xué)作為旗手如：[12，薛丁]，[45，李強(qiáng)]，[56，徐梓]，[66，鮑杰]，[77，黃怡]，[80，余澍]，[97，金維]，[101，方茹]，[120，陳昀]，現(xiàn)在某位家長(zhǎng)想知道方茹同學(xué)是否被選到，如果選到又是第幾個(gè)旗手，為了解決這個(gè)問(wèn)題，可以使用插補(bǔ)查找算法來(lái)解決問(wèn)題。例如：查找方茹，需要輸入101進(jìn)行查找，具體如圖所示：
（1）在題目所示案例中，若使用插補(bǔ)查找算法查找45，則該過(guò)程中訪問(wèn)到的數(shù)據(jù)依次為
56 45
56 45
；
（2）實(shí)現(xiàn)上述功能的Python程序如下，請(qǐng)?jiān)跈M線處填入合適的代碼。
