【数据结构】有序向量的查找——二分查找（折半查找）
来源于《数据结构（上）》邓俊辉
https://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/
本节主要讲数据结构的第二章向量部分，介绍有序向量的查找操作的基本框架，以及给出二分查找的基本算法。
1、有序向量的查找
之前无序向量的查找，需要从后往前依次找，直到找到对应的值
对于有序向量来说，也需要三个参数，查找对象e，和查找区间lo，hi
对于有序向量查找的一个统一接口如上图，其语义也就是在区间中找到目标元素e
但是问题出现了，如果出现特殊情况怎么办？
-目标元素不存在，返回什么？
-目标元素存在多个，返回哪一个？
2、有序向量查找的语义定义
因为出现特殊情况，所以有序向量的search也需要进行统一的定义，来设计算法。
给出最基本的规范：应该便于有序向量自身的维护：V.insert(1+V.search(e), e)
-即使失败，也应该给出新元素适当插入位置
-若允许重复元素，每一组也应该按照其插入次序排列
所以，为了满足上述规范，给出有序向量查找的约定：
这个约定中，其实就是返回了查找元素的秩
3、有序向量二分查找（版本A）
(1)二分查找（版本A）的原理
二分查找的基本思想是减而治之的思想，也就是通过任意元素为界，将查找区间分三份
那么这种算法就存在三种情况：
为了防止数据两边查找的不平衡，这里基础版使用二分折半查找的策略，也就是轴点mi取做中点
这样，每经过至多两次比较，要么能够命中，要么问题规模缩减一半
(2)二分查找（版本A）的实现
每一次都循环判断当前区间是否有效
轴点选择那里，右移一位相当于除二
注意到：一个代码习惯是，尽可能使用小于号<，因为这样就像画的图那样便于理解和阅读
(3)二分查找（版本A）的实例
按照递归的思路，不断查找，可以看上面的一个成功命中和失败的例子
每次递归都会进行比较，也许是比较一次或两次就可以进行下一次递归，而下一次递归规模减半，通过线性递归公式求解出来的结果，该算法复杂度为O(logn)，大大优于顺序查找
当然通过递归跟踪，也不难看出，递归总共其实也总共是需要logn次的，也可以求出复杂度
(4)二分查找（版本A）的查找长度
为了更细致的比较复杂度，也就不仅仅需要从渐进复杂度来理解算法。
在这里需要考察关键码的比较次数，也就是查找长度（search length）
通常，需要分别针对成功和失败的情况，而且从最好，最好，以及平均等角度评估。
从上述递归跟踪图中能够推算出，递归跟踪的平均查找长度大致为O(1.50*logn)
也就是这个图中推算出，成功或者失败，他的查找长度计算结果大致等于1.50*logn
点点关注~计算机学习不迷路