---
# System prepended metadata

title: 插補搜索

---

# 插補搜索

## 簡介

插補搜尋是二分搜索的優化，主要是在中間值上套用公式去計算，公式的原理是，如果輸入的資料呈現線性成長的話，就可以藉由插補搜尋法的公式，找到與目標下標的近似或是該下標，但是如果輸入的資料數值之間落差很大的話，插補搜尋就無法呈現它的優勢。

## 公式

```cpp=
int mid = lower + (target - nums[lower]) * (upper - lower) / nums[upper] - lower
```