查找_二分查找

简述

也叫折半查找，性能优异。

但是所查找的数列必须是有序序列。

复杂度

• 时间复杂度
  • log2(N)

实现

非递归实现

递归实现

插值查找

1. 二分查找每次都会计算出一个mid，然后拿这个mid的值去做比较

$$
mid = \frac{(low+high)}{2}
$$

$$
mid = \frac{low+high}{2} = low + \frac{1}{2}(high - low)
$$

2. 插值查找本质就是对上面这个算法进行优化，方案如下：

$$
mid = low + \frac{key - a[low]}{a[high] - a[low]}(high - low)
$$

3. 示例，a[11] = {0,1,16,24,35,47,59,62,73,88,99}。

   1. 查找16，key为16
   2. low为1，high为10，a[low]为1，a[high]为10

4. 插值查找是根据要查找的关键字key与查找表中最小最大记录的关键字比较后的查找方法，其核心就在于上面这个公式。