- 一般二分、斐波那契分、两边都不管mi的写法
- 旋转数组：模拟
二分查找（以单调递增为例）
初版
原理
- e < x: 则e若存在必属于左侧子区间，故可（减除\(s [ mi,hi )\)并）递归深入\(s[lo，mi)\)
- x < e: 则e若存在必属于右侧子区间，亦可（减除\(s [ lo,mi ]\)并）递归深入\(s(mi，hi)\)
- e = x: 已在此处命中，可随即返回 #### 代码
1
2
3
4
5
6
7
8
9
10
11
12template <typename T>
static Rank binarySearchA(T *S, const T a, Rank lo, Rank hi)
{
while (lo < hi)
{
Rank mi = (lo + hi) >> 1;
if (a < S[mi]) hi = mi;
else if (S[mi] < a) lo = mi;
else return mi;
}
return -1;
}
优化1：斐波那契查找
原理
- 原版中，转向左、右分支前的关键码比较次数不等（左一次，右两次）
- 宁愿左边多递归几层来平衡一下
- 若有 \(n = fib(k)-1\)，则可取 \(mi = fib(k-1)-1\)，前、后子向量的长度分别为 \(fib(k-1)-1\)、\(fib(k-2)-1\) #### 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15template <typename T>
static Rank fibSearch(T *S, const T a, Rank lo, Rank hi)
{
for (Fib fib(hi - lo); lo < hi;)
{
// Rank mi = (lo + hi) >> 1;
while (hi - lo < fib.get()) fib.prev();
Rank mi = lo + fib.get() - 1; // 找到合适的轴点
if (a < S[mi]) hi = mi;
else if (S[mi] < a) lo = mi;
else return mi;
}
return -1;
}
优化2：两分支的二分查找
原理
- 原版中，转向左、右分支前的关键码比较次数不等（左一次，右两次）
- 如果直接只比较一次，就没有这个问题了
- e < x: 则e若存在必属于左侧子区间s[1o, mi)，故可递归深入
- x <= e: 则e若存在必属于右侧子区间s[mi, hi)，亦可递归深入
- 直到hi - lo = 1，才判断是否命中 ##### 代码
1
2
3
4
5
6
7
8
9
10template <typename T>
static Rank binarySearchB(T *S, const T a, Rank lo, Rank hi)
{
while (1 < hi - lo)
{
Rank mi = (lo + hi) >> 1;
a < S[mi] ? hi = mi : lo = mi;
}
return a == S[lo] ? lo : -1;
}
优化3：两边都嫌弃mi的两分支二分查找
原理
- 转入右侧子向量时，左边界取mi+1（而非mi） #### 代码 #### 问题
1
2
3
4
5
6
7
8
9
10template <typename T>
static Rank binarySearchC(T *S, const T a, Rank lo, Rank hi)
{
while (hi < lo)
{
Rank mi = (lo + hi) >> 1;
a < S[mi] ? hi = mi : lo = mi + 1;
}
return lo - 1;
}
两边都不要mi，那如果mi命中了怎么办？ 答：mi如果命中，那后边的查找都是白忙活，本质就是等结束。但是在白忙活的过程中，lo是不会变的，因为每次查找都会发现target小了，得在左侧子向量找。这样，lo就被保留下来了。最后返回的lo-1不就是刚开始的mi吗，没毛病。
那mi没有命中怎么办？（指target比mi大而比mi+1小），这样返回mi没问题吗？ 答：没问题。须知，查找的语义约定为：查找e，返回不大于e且秩最大的元素。这种写法是符合语义约定的，之前的各种失败返回-1的算法反而不符合。
二分·旋转数组
- 旋转数组：升序向量，截取前边一段接到后边 ## T31 旋转向量元素不重复
