单片机上实现二分查找+线性插值计算

项目中需要在现有数据表格里面搜索数据，并做线性插值计算。

线性插值计算原理简单，即两点之间近似为直线，求直线上的某一点坐标即可。

已知点（x0,y0）、（x1,y1）求取插值点x处的y。

( y-y0)/(x-x0)=(y1-y0)/(x1-x0)，就可以求出该点坐标

考虑超出表格范围的数据也做线性插值计算。

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素，复杂度：O（lg n），n为要查找的元素个数。

二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行lg n次分区。对于二分查找，这表示最终可能在最坏的情况下执行的检查的次数：例如，在没有找到目标时。所以二分查找的时间复杂度为O（lg n）。

二分查找代码如下。

根据自己的需求，插值计算还可以是对数插值，指数插值，抛物线插值等等。