二分查找和斐波那契查找

二分查找

int binSearch(int* arr, int lo, int hi,int target)
{
	while (lo < hi){
	int mid = lo + ((hi - lo) >> 1);
	if (arr[mid] > target) hi = mid;
	else if (arr[mid] < target) lo = mid + 1;
	else  return mid;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10

通过选择中点，不断迭代

斐波那契查找

与二分查找思想一致，划分点选取不一样
二分查早的话，一次迭代有三种情况，
中点值和目标值进行 > 比较后，满足则进入左半区间，
不满足，进入 < 比较，满足则进入右半区间，
不满足，则相等，返回

所以这样的话，想进入左半区间，进行一次比较，想进入右半区间，会进行两次比较，右侧比较会多
所以改进方法：调整左、右区域的宽度，适当地加长（缩短）左（右）子向量

class Fib {
private:
	int fibNumber;
	int Rank;
	int* arr;
public:
	Fib(int n)
	{
		this->fibNumber = n + 1;
		this->arr = new int[this->fibNumber];
		for (int i = 0; i < this->fibNumber; i++) {
			arr[i] = fib(i);
			this->Rank = i;
		}
	}
	int fib(int n)
	{
		int f = 0, g = 1;
		while (n-- > 0) {
			g += f; f = g - f;
		}
		return f;
	}
	~Fib() 
	{
		if (arr != NULL)
			delete[] arr;
		arr = NULL;
	}

	int get() { return this->arr[this->Rank]; }
	void prev() { this->Rank--; }

};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Fib为斐波那契类，构造函数为创建一个0到n的斐波那契数列，总共n+1项
get（）函数为返回当前索引的斐波那契数
prev（）函数为索引向前移动一项，即前一项的斐波那契数。

int fibSearch(int* arr, int lo, int hi, int target)
{
	Fib fib(hi - lo);
	while (lo < hi)
	{
		while (hi - lo  < fib.get()) fib.prev();
		int mid = lo + fib.get() - 1;
		if (arr[mid] > target) hi = mid;
		else if (arr[mid] < target) lo = mid + 1;
		else return mid;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

先实例化一个Fib类，初始化为一个hi-lo个数的斐波那契数列，
假设目标数列即要进行二分查找的数列在lo到hi索引之间有n个数（左闭右开），则初始化的斐波那契数列也是n个数

while (hi - lo  < fib.get())
1

这个循环中的比较是为了找出fib（k-1），数列中总数为fib（k）-1

二分查找改进B

原二分法问题，左右方向不平衡
斐波那契查找改进其一，调整前、后区域的宽度，适当地加长（缩短）前（后）子向量
实际上还有另一更为直接的方法，即令以上两项的常系数同时等于
1。也就是说，无论朝哪个方向深入，都只需做1次元素的大小比较，其二，统一沿两个方向深入所需要执行的比较次数，比如都统一为一次

在每个切分点A[mi]
处，仅做一次元素比较。具体地，若目标元素小于A[mi]，则深入前端子向量A[lo, mi)继续查
找；否则，深入后端子向量A[mi, hi)继续查找。

int binSearchB(int* arr, int lo, int hi, int target)
{
	while (hi-lo>1) {//区间长度不是缩短为0时退出循环，而是区间长度缩短为1时退出循环
		int mid = lo + ((hi - lo) >> 1);
		//if (arr[mid] > target) hi = mid;//hi这面是开区间
		//else  lo = mid;
		(arr[mid] > target) ? hi = mid : lo = mid;
	}
	/*if (arr[lo] == target)
		return lo;
	else return -1;*/
	return (arr[lo] == target) ? lo : -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二分查找改进C

在有序向量中的查找，遇到重复的元素时会返回秩最大的那个，上述查找无法实现这个功能，因此加以改进

int binSearchC(int* arr, int lo, int hi, int target)
{
	while (hi > lo) {//区间长度缩短为0时退出循环
		int mid = lo + ((hi - lo) >> 1);
		(arr[mid] > target) ? hi = mid : lo = mid + 1;
	}
	return --lo;
}
1
2
3
4
5
6
7
8

版本C与版本B的差异，主要有三点。
首先，只有当有效区间的宽度缩短至0（而不是1）时，查找方告终止。
另外，在每次转入后端分支时，子向量的左边界取作mi + 1而不是mi。
表面上看，后一调整存在风险，此时只能确定切分点arr[mid]＞target ，“贸然”地将arr[mi]排除在进一步的查找范围之外，似乎可能因遗漏这些元素，而导致本应成功的查找以失败告终。
但其实没问题