- 一般二分、斐波那契分、两边都不管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 旋转向量元素不重复