邓俊辉《数据结构》→ “2.6.5 二分查找（版本A）”之“成功查找长度”递推式推导

【问题描述】
邓俊辉的《数据结构（C++语言版）（第3版）》（ISBN：9787302330646）中，开始于第48页的“2.6.5 二分查找（版本A）”内容在第50页详述了“成功查找长度”的递推式，但此递推式乍一看令人费解。故为了说明问题，进行一些约定并详述如下：
● 既然是二分查找，所以给定的序列必定是有序的。
● 不失一般性，约定有序序列的长度 ，这样便可构建一个高度为 k 的满的二分查找树。
● 设 C(k) 表示高度为 k 的满的二分查找树中所有元素的查找长度总和。此时，问题就可以用递归方法求解。即 k 层的满二叉树，可以转化为左右两个 k-1 层的满二叉树。 依据邓俊辉《数据结构（C++语言版）（第3版）》（ISBN：9787302330646）中“2.6.5 二分查找（版本A）”的算法陈述，可知：
（1）第 k 层的查找长度为2（也即 ）；
（2）且稍加观察会发现左面的 k-1 层的子树所有元素的查找长度都会相对于以第 k-1 层为顶层时的查找长度多1（左子树共多 ）。
（3）同样右面的 k-1 层的子树所有元素的查找长度都会相对于以第 k-1 层为顶层时的查找长度多2（右子树共多 ）。
所以，根据递归算法的设计思想，需要把这些长度补上，共同构成 C(k)。

综上，可得 C(k) 的递推公式如下：

化简得：

若令，
则有：


故利用上文得出的 ，可进一步得出：


于是将  代入  可得：


从而可得平均查找长度为：
忽略掉低阶项、常数项、系数项，可得本版本的二分查找的平均查找长度的时间复杂度为：
​​​​​​​

【参考文献】
https://ask.csdn.net/questions/699067
https://www.bilibili.com/video/BV1C54y1L7JM/
https://www.bilibili.com/video/BV1C54y1L7JM/?p=76&vd_source=fea4f130ba05b1c873be1db0c639fc56
https://blog.csdn.net/hnjzsyjyj/article/details/133100051
https://blog.csdn.net/qq_33499861/article/details/105103708