# 插補搜索 ## 簡介 插補搜尋是二分搜索的優化，主要是在中間值上套用公式去計算，公式的原理是，如果輸入的資料呈現線性成長的話，就可以藉由插補搜尋法的公式，找到與目標下標的近似或是該下標，但是如果輸入的資料數值之間落差很大的話，插補搜尋就無法呈現它的優勢。 ## 公式 ```cpp= int mid = lower + (target - nums[lower]) * (upper - lower) / nums[upper] - lower ```