devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法 | 【二分查询】进阶与优化 ——区间查询、递归查询、0.618优化..._二分化查询优化

作者：不正经 | 2024-03-13 20:46:23

赞

踩

二分化查询优化

二分查询也称折半查找（Binary Search）、二分查找，它是一种效率较高的查找方法。但是，二分查询要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

对于一个顺序存储结构我们最熟悉的莫过于数组了，在使用数组对其内部的元素进行随机访问是非常高效的。并且数组的使用也是非常方便，相信对于数组的遍历以及查找的算法对于大家来说都轻而易举。但是呢，有时候在一些简单小问题中也会有令我们不容忽视的存在。

下面，我们准备了两个示例，分别通过递归和循环的方式设计算法。

文章目录

示例1：有一个整型数组，数值无序，使用循环和递归完成打印和查询。

对于数组的遍历我就不多bb了，直接上代码：

#include <iostream>
#include <ctime>
using namespace std;

/*
问题：有一个整型数组，数值无序，使用循环和递归完成打印和查询。
*/

// 循环实现
void print(const int *ar, int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << ar[i] << " ";
	}
	cout << endl;
}
void Print_Ar(const int* ar, int n)			/* 打印 */
{
	if (NULL == ar || n < 1) return;
	print(ar, n);
}

int find(const int* ar, int n, int num)
{
	int i = n;
	while (i > 0 && ar[i - 1] != num)
	{
		--i;
	}
	return i-1;
}
int Find_Ar(const int* ar, int n, int num)	/* 查询 */
{
	if (NULL == ar || n < 1) return -1;
	find(ar, n, num);
}

// 递归实现			//倒序打印
void print_r(const int* ar, int n)
{
	if (n > 0)
	{
		cout << ar[n - 1] << " ";
		print_r(ar, n - 1);	
	}
}
void Print_r(const int* ar, int n)
{
	if (NULL == ar || n < 0) return;
	print_r(ar, n);
	cout << endl;
}

//						正序
void print_r2(const int* ar, int n)
{
	if (NULL == ar || n < 1) return;
	if (n > 0)
	{
		print_r2(ar, n - 1);
		cout << ar[n - 1] << " ";
	}
}
void Print_r2(const int* ar, int n)
{
	if (NULL == ar || n < 0) return;
	print_r2(ar, n);
	cout << endl;
}

// 查询			根据Find_Ar()修改所得
int find_r(const int* ar, int n, int val)
{
	if (n <= 0 || ar[n - 1] == val)
	{
		return n - 1;
	}
	else
	{
		return find_r(ar, n - 1, val);
	}
}
int FindVal(const int* ar, int n, int val)
{
	if (NULL == ar || n < 1) return -1;
	else return find_r(ar, n - 1, val);
}

int main()
{
	/* 随机生成数组元素 */
	srand((unsigned)time(NULL));
	int arr[10] = {};
	int len = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < len; ++i)
	{
		arr[i] = rand() % 100 + 1;
	}


	Print_Ar(arr, len);	/*打印*/
	int index1 = Find_Ar(arr, len, arr[5]);
	if (index1 != -1)	cout << index1 << endl;

	Print_r(arr, len);	/*打印*/
	Print_r2(arr, len);
	int index2 = FindVal(arr, len, arr[5]);
	if (index2 != -1)	cout << index2 << endl;

	return 0;
}

  • 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
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
示例2：有一个整型数组，如果数组有序，使用二分查询。

对于一个有序的数组，非常适合使用二分查找。二分查找思想为折半，如我们的猜数游戏。

模型如下：

12345678910
  • 如果我们选择从 “1” 位置作为查找的起始点，那么我们与1之间的距离为0，与10之间的距离为10，也就是说如果我们找1，那么只需一步就能找到，而我们要找10需要10步才能找到。最坏的情况下我们需要找10次。
  • 如果我们选择从 “5”或“6” 位置作为查找起始点，那么我们与1和10之间的距离为5，并且如果我们查找的方式为每次取其中间位置的数跳跃式的查找，它在最好的情况在找一次，最坏的情况下只需要找3次。

事实上第二种的查找方式就用的是我们二分查找的思想，这仅仅是在1~10之间的查找范围，在某种程度上来说，查找范围越大，二分查找相对于普通的遍历查找优势就越明显。

时间复杂度：
由于二分查找每次取中位查找，对于规模为n的线性表来说，取值规律为： 1 2 、 1 4 、 1 8 、 1 16   . . .   . . . 1 2 m \frac{1}{2}、\frac{1}{4}、\frac{1}{8}、\frac{1}{16} \ ...\ ...\frac{1}{2^m} 21​、41​、81​、161​ ... ...2m1​ 。
分析：

  • 第一次 a r r [ n 2 ] arr[\frac{n}{2}] arr[2n​]
  • 第二次 a r r [ k ∗ n 4 ] arr[k*\frac{n}{4}] arr[k∗4n​] ，其中 k = 1 或 3 k=1或3 k=1或3，K表示取左半段或右半段
  • 第三次 a r r [ k ∗ n 8 ] arr[k*\frac{n}{8}] arr[k∗8n​] ，其中 k = 1 、 3 或 5 、 7 k=1、3或5、7 k=1、3或5、7，K表示在第二次折半后，取左半段或右半段。

前三次查找模型大致如下：

0 1 8 ∗ n \frac{1}{8}*n 81​∗n 1 4 ∗ n \frac{1}{4}*n 41​∗n 3 8 ∗ n \frac{3}{8}*n 83​∗n 1 2 ∗ n \frac{1}{2}*n 21​∗n 5 8 ∗ n \frac{5}{8}*n 85​∗n 3 4 ∗ n \frac{3}{4}*n 43​∗n 7 8 ∗ n \frac{7}{8}*n 87​∗n n n n
左顶点第一次查找位置右顶点
左顶点第二次查找位置… …右顶点
左顶点第三次查找位置… …… …右顶点
左顶点右顶点
  • 第…次
  • 第 m 次 a r r [ k ∗ n 2 m ] arr[k*\frac{n}{2^m}] arr[k∗2mn​]

在最坏的情况下，假设查找了 m 次，整个数组只剩下一个数据，那么可列等式：
n 2 m = 1 \frac{n}{2^m} = 1 2mn​=1 或者 k ∗ n 2 m = k k*\frac{n}{2^m} = k k∗2mn​=k
则： m = log ⁡ 2 n m = \log_2{n} m=log2​n
因此最坏情况下的时间复杂度为： O ( log ⁡ 2 n ) O(\log_2{n}) O(log2​n)

下面是代码实现：

#include <iostream>
#include <ctime>
using namespace std;

/*
问题：有一个整型数组，如果数组有序，使用二分查询。。
*/

int MidFind(const int* ar, int n,int val)
{
	int left = 0, right = n - 1;
	while (left <= right) 
	{
		int mid = (left + right) / 2;
		if (val < ar[mid])
		{
			right = mid - 1;
		}
		else if (val > ar[mid])
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

int main()
{
	int arr[] = { 12,23,34,45,56,67,78,89,90,100 };
	int len = sizeof(arr) / sizeof(arr[0]);

	int index = MidFind(arr, len, 23);
	if (-1 != index)
		cout << index << endl;
	return 0;
}

  • 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
  • 37
  • 38
  • 39
  • 40

代码非常简单，但是你认为这样就完了吗？No NO No
如果在面试中面试官让你写一个二分查询，你写成这样的代码。那么很遗憾，回家等通知吧。

二分查询 | 面试官找茬，常见错误及代码的查漏补缺

这段二分查找代码说你写错吧，还不至于，可是说好吧，也还远远算不上。假如面试官针对你的代码找茬，你如和应对，如果没有天生机制过人的大脑和聪明才智的话，到时候就只能硬着头皮上了。好在现在还没有面试官对我们找茬，那我们就笨鸟先飞，先来个代码自省。俗话说的好，不打无把握的仗，“排除一切不可能后,剩下的就是真相”。同理，让我们将所有的问题都排查掉，让面试官无茬可找。下面让我们带入面试官的角色进行找茬，从不同角度分析这段代码。

找茬：

  1. 问题1：如果传入的参数是 ar == NULL 或 n < 1 情况怎么办？
    解决：if (NULL == ar || n < 1) return pos;
  2. 问题2：int mid = left + right;
    这句代码乍一看没有问题，可是你有没有考虑过整型溢出的问题。如果说我们要查询的规模是一个20亿的范围，而我们要查找的数恰好位于10亿到20亿之间，那么当我们用 left + right 确定 mid 的范围时就会超出 int 的范围。 ps：int 上届为20亿(231)左右。
    解决：int mid = left + (right - left + 1) / 2;这里的除以2操作，也可以用位运算 >>1 代替。
  3. 问题3：如果数组不仅有序还含有重复值，要求 求出其第一个满足要求的下标或最后一个满足要求的下标。
    解决1：查找第一个满足要求的值 while (left < mid && ar[mid - 1] == ar[mid]) { --mid; }
    解决2：查找最后一个满足要求的值 while (mid < right && ar[mid] == ar[mid + 1]) { ++mid; }
    解决3：返回区间范围，定义结构struct Pair{ int left; int right; };，把解决方案1，2中的值保存在Pair结构中返回。

如上，我们找出了3处问题，并且我们针对问题分别设计出了解决方案，现在修改代码如下：

#include <iostream>
#include <ctime>
using namespace std;

/*
问题：有一个整型数组，如果数组有序，使用二分查询。。
解决：添加出错判断、修改可能溢出代码段、增加筛选重复项功能
*/

/* 返回较小下标 */
int MidFind_L(const int* ar, int n, int val)
{
	int pos = -1;
	if (NULL == ar || n < 1)	return pos;		/* return -1*/
	int left = 0, right = n - 1;
	while (left <= right)
	{
		int mid = left + (right - left + 1) / 2;		/* 修改 */
		if (val < ar[mid])
		{
			right = mid - 1;
		}
		else if (val > ar[mid])
		{
			left = mid + 1;
		}
		else
		{
			while (left < mid && ar[mid - 1] == ar[mid]) { --mid; }
			pos = mid;
			break;
			/* 2021/8/16更新：优化，将线性的查找变成二分的查找
			// 取最左边的数据
            if (mid <= left || val != arr[mid - 1])
            {
                pos = mid;
                break;
            }
            right = mid - 1;
            */
		}
	}
	return pos;
}

struct Pair		/* 存放下标区间数据结构 */
{
	int left; 
	int right; 
};
/* 返回区间 */
Pair MidFind_du(const int* ar, int n, int val)
{
	int retL = -1;
	int retR = -1;
	if (NULL == ar || n < 1)	return { retL,retR };		/* return {-1,-1}*/
	int left = 0, right = n - 1;
	while (left <= right)
	{
		int mid = left + (right - left + 1) / 2;		/* 修改 */
		if (val < ar[mid])
		{
			right = mid - 1;
		}
		else if (val > ar[mid])
		{
			left = mid + 1;
		}
		else
		{
			retL = mid;
			retR = mid;
			while (left < mid && ar[mid - 1] == ar[mid]) { --mid; }
			retL = mid;

			mid = retR;
			while (mid < right && ar[mid] == ar[mid + 1]) { ++mid; }
			retR = mid;

			break;
		}
	}
	return { retL ,retR };
}

int main()
{
	int arr[] = { 12,12,12,23,23,34,45,45,56,67,78,89,90,100,100 };
	int len = sizeof(arr) / sizeof(arr[0]);

	int index = MidFind_L(arr, len, 12);	/* 输出第一满足要求的下标  */
	if (-1 != index)
		cout << index << endl;

	Pair pr =  MidFind_du(arr, len, 12);	/* 输出满足要求的区间  */
	if (-1 != pr.left || -1 != pr.right)
		cout << "[" << pr.left << "," << pr.right << "]" << endl;

	return 0;
}

  • 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
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

递归：如果面试官此时又问，你能不能将此程序改为递归的方式求解 。

嗯，这个倒是不难，递归和循环的关系就像是两双胞胎，非常相似 。我们细心分析就会发现递归实际上也是一种循环，无非是自己调用自己罢了。下面就是二分查询的递归实现代码：

#include <iostream>
#include<algorithm>  
#include <ctime>
using namespace std;

/*
	递归实现二分查找
*/

int Find(const int* ar, int left, int right, int val)
{
	int pos = -1;
	if (left <= right)
	{
		int mid = left + (right - left + 1) >> 2;
		if (val < ar[mid])
		{
			pos = Find(ar, left, mid - 1, val);
		}
		else if (val > ar[mid])
		{
			pos = Find(ar, mid + 1, right, val);
		}
		else
		{
			while (mid > left &&  ar[mid - 1] == val)--mid;
			pos = mid;
		}
	}
	return pos;
}
int FindVal_r(const int* ar, int n, int val)
{
	if (NULL == ar || n < 1)	return -1;
	else return Find(ar, 0, n - 1, val);
}

int main()
{
	int arr[] = { 11,11,11,12,12,13,14,15,16,17,18,19,20 };
	int len = sizeof(arr) / sizeof(arr[0]);

	int index = FindVal_r(arr, len, 12);

	cout << index;

	return 0;
}

  • 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
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

在解决了面试官的找茬后，面试官又问道，能不能尝试着优化一下呢 。什么？不会，那没事了，回去等通知吧。（开个玩笑）
以上代码基本上就是我们普通人的极限了，那么想要进阶，想要优化就只能靠它了。你问我他是谁？还能有谁，当然是我们算法的好基友数学了。

所以说，不想当数学家的程序猿，不是一个好的算法工程师。

二分查询 | 进阶：查询效率优化与黄金分割点 0.618

如表中所见，有 6 个数据，我们在寻找mid时采用的是 mid = left + (right - left + 1) / 2 的方法取中间值。

index012345
data123456

对于 mid 等分的问题分析
其中，mid 的取值表达式也可以写成 mid = left + (right - left + 1) * 0.5 。在这段代码中，我们把 left - right 中的数值折半，或者叫等分，通过这种方式获得某段范围内的中间值。但是对于上表中的这 6 个数据而言，始终是无法等分的，在取中间值时要么最终取偏左的下标 2，要么取偏右的下标 3。

而我们常规的整除运算，取值一律偏左。如 2 除以 2 结果是1，3 除以 2 结果也是1 。而对于数组来说，下标都是从0开始的，也就是说对于长度为2的数组｛下标 0，1｝， m i d = ( 1 − 0 + 1 ) / 2 = 1 mid = (1-0+1)/2 = 1 mid=(1−0+1)/2=1，长度为3的数组 ｛下标 0，1，2｝， m i d = ( 2 − 0 + 1 ) / 2 = 1 mid = (2-0+1)/2=1 mid=(2−0+1)/2=1 。
m i d = { 1 n = 2 , 下 标 { 0 , 1 } 2 n = 3 , 下 标 { 0 , 1 , 2 } mid=

{1n=2,下标{0,1}2n=3,下标{0,1,2}
mid={12​n=2,下标{0,1}n=3,下标{0,1,2}​

对于本例来说 m i d = 0 + ( 5 − 0 + 1 ) ∗ 0.5 = 3 mid = 0 + (5-0+1) * 0.5 = 3 mid=0+(5−0+1)∗0.5=3 ，也是取的偏右的值，或者说下标偏大的值 。
总结：常规二分查找去中间值时采用的下标偏大原则，并不是真正意义上的等分。

m i d = { 下 标 偏 大 问 题 规 模 为 偶 数 下 标 等 分 问 题 规 模 为 奇 数 mid=

{下标偏大问题规模为偶数下标等分问题规模为奇数
mid={下标偏大下标等分​问题规模为偶数问题规模为奇数​

左右边界查询效率的问题分析
那么，理论上对于偶数规模的问题而言，在查找右边的数据时会比查找左边的数据要快。比如对于一个有序数组 a r r [   ] = 1 , 2 , 3 , 4 , 5 , 6 arr[\ ] = {1,2,3,4,5,6} arr[ ]=1,2,3,4,5,6 而言。查询最左边的 1，查询次数为 3 次，查询最右边的数据 6，查询次数为 2 次。具体查询过程见下表：

  • 查询最左边的数据 1，下标为为0，即 a r r [ 0 ] = 1 arr[0] = 1 arr[0]=1 ，下图仅显示下标，其中 i 、 j 、 k i、j、k i、j、k 分别表示第一次，第二次、第三次 mid 的位置。
012345
i
j
k
  • 查询最右边的数据 6，下标为为5，即 a r r [ 5 ] = 6 arr[5] = 6 arr[5]=6 ，下图仅显示下标，其中 i 、 j i、j i、j 分别表示第一次，第二次 mid 的位置。
012345
i
k

归根结底，我们无法实现真正的等值折半。那么有没有一种解决方案可以优化取中间值的步骤呢？

最后我在中国知网找到了一片论文，名为黄金分割算法与顺序表查找。 知网链接：[1]邹永林,唐晓阳.黄金分割算法与顺序表查找[J].福建电脑,2002(02):16-17.
 论文中介绍了一种黄金分割算法，比起我们的二分查询算法更加高效。此外，此篇论文是提供免费下载的，想仔细了解的同学可以去中国知网阅读或下载。

下面引用自论文中部分内容：
2.1基本思想:
1.利用黄金分割值(DID)将查找区(设low.high分为查找区的起点和终点)分割成三个更小的查找区(其分割点分别为P1 = low + 0.618 X ( high - low ) 和 P2 = high - (0.618 X ( high - low ))分别为: [low,p2]、[p2 ,p1 ]、[p1 ,high]; 。
2.待查找的关键字值与P1 或P2 进行比较,若与某个分割点值相等,则查找成功,此分割点的值便为待查找关键字的位置,算法结束。
3. 否则,待查找的关键字可能在被P1、P2分割成三个分割区中的某个分割区PART ,并修改分割区PART的low和high的值。若low<=high则转向1) 继续查找，否则结束算法,查找不成功。
3.算法分析
4. 此算法过程可产生一棵三叉排序树。设有n个有序关键字值,因此,查找不成功进行比较的次数至多不超过树的深度即「log3n+ 1」;
5. 同理,查找成功进行比较的次数至多不超过树的深度即「log3n+1];
6. 黄金分割算法与二分(折半)查找算法比较,无论查找成功或不成功,虽然查找次数属于相同数量级,但黄金分割算法分割查找区间的效率较高,当n相当大时,黄金分割算法查找效率优于二分查找算法。

在该篇论文中提到，待查找区间被 p1、p2分割为三个区间， 每一次查找同时可以找到两个位置点（p1，p2），相比二分查询每次只能查询一个值确实高效许多。这篇论文所讲算法思想为黄金分割点，算法名为黄金分割算法 。

黄金分割：百度词条给出解释是，将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为0.618。而0.618这个数字被誉为神圣比例，黄金分割被称为神圣分割，并且我注意到一个细节，“将整体一分为二” 。我们之前已经知道二分法无法使我们的区间被真正意义上的等分，而我们通过黄金分割算法给我们提供了一种新的思路，是否我们可以用黄金分割比例来划分区间，优化折半效率呢？

最后查阅资料，发现原来数学家 华罗庚(优选法) 已经证明了，每次取中点的试验方法并不是最好的方法；每1次取试验区间的 0.618 处去做试验的方法，才是最好的，称之为“优选法”或“0.618 法”。 华罗庚证明了，这可以用较少的试验次数，较快地逼近最佳方案。

既然找到了比“二分”更好的“0.618”法进行折半，那么代码就改写就非常简单了，只需将代码中的 * 0.5 改成 * 0.618 即可。

int mid = left + (right - left + 1) * 0.618;

  • 1

实践是检验真理的唯一标准，下面我们通过对规模为 10万 的有序数组进行两种方案的二分查找，以所用时间为评判标椎，测试两个查找算法的效率。代码如下：

#include <iostream>
#include<algorithm>			/* sort() 排序算法 */
#include<windows.h>			/* 高进度时控函数 */
#include<sys/timeb.h>		/* 获得毫秒级时间 struct timed */

using namespace std;

/*
	测试两种二分查找的效率
	对规模为 10万 有序数组，进行二分查找测试，并统计各自所用时间。
*/

/* 使用等分（*0.5）实现的查找 */
int MidFind(const int* ar, int n, int val)
{
	int pos = -1;
	if (NULL == ar || n < 1)	return pos;
	int left = 0, right = n - 1;
	while (left <= right)
	{
		int mid = left + (right - left + 1) / 2;
		if (val < ar[mid])
		{
			right = mid - 1;
		}
		else if (val > ar[mid])
		{
			left = mid + 1;
		}
		else
		{
			while (left < mid && ar[mid - 1] == ar[mid]) { --mid; }
			pos = mid;
			break;
		}
	}
	return pos;
}

/* 使用黄金分割点（*0.618）实现的查找 */
int NiceMidFind(const int* ar, int n, int val)
{
	int pos = -1;
	if (NULL == ar || n < 1)	return pos;
	int left = 0, right = n - 1;
	while (left <= right)
	{
		int mid = left + (right - left + 1) * 0.618;
		if (val < ar[mid])
		{
			right = mid - 1;
		}
		else if (val > ar[mid])
		{
			left = mid + 1;
		}
		else
		{
			while (left < mid && ar[mid - 1] == ar[mid]) { --mid; }
			pos = mid;
			break;
		}
	}
	return pos;
}

// 统计一次查找时，使用0.5的二分查找时间，和使用0.618的查找时间。
int OneTest(int* arr, double& time1, double& time2, int n)
{
	//srand((unsigned)time(NULL));		/* 注意：如果间隔时间小于1s，将使用相同的随机数种子 */
	timeb tm;
	ftime(&tm);
	srand(tm.millitm);		/* 毫秒级随机数种子 */
	for (int i = 0; i < n; ++i)
	{
		arr[i] = rand() % 1000 + 1;
	}
	sort(arr, arr + n);		// 排序

	int target = rand() % 1000 + 1;

	/*64位有符号整数 联合体 用来保存高精度时间值*/
	LARGE_INTEGER nFreq;
	LARGE_INTEGER nBeginTime;
	LARGE_INTEGER nEndTime;

	QueryPerformanceFrequency(&nFreq);

	/* 测试 0.5 效率 */
	QueryPerformanceCounter(&nBeginTime);//开始计时 
	int index1 = MidFind(arr, n, target);
	QueryPerformanceCounter(&nEndTime);//停止计时  
	time1 = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;//计算程序执行时间单位为s  

	/* 测试 0.618 效率 */
	QueryPerformanceCounter(&nBeginTime);//开始计时 
	int index2 = NiceMidFind(arr, n, target);
	QueryPerformanceCounter(&nEndTime);//停止计时  
	time2 = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;//计算程序执行时间单位为s  

	if (index1 != index2)	return -1;
	else return index1;

}

// 测试多组数据，这里设置为100次，并记录有无查找出错情况
int Tests(int* arr, double& time1, double& time2, int n)
{
	int count = 0;
	int times = 100;
	while (times--)
	{
		int ind = OneTest(arr, time1, time2, n);
		if (ind == -1)	count++;
	}
	return count;
}

int main()
{
	const int LEN = 100000;
	int arr[LEN] = {};

	double time1 = 0;		// 0.5   用时
	double time2 = 0;		// 0.618 用时

	// 测试十组数据
	int times = 10;
	while (times--)
	{
		int inErr = Tests(arr, time1, time2, LEN);
		cout << "0.5：\t 用时 " << time1 << endl;
		cout << "0.618：\t 用时 " << time2 << endl;
		cout << "匹配失败次数  " << inErr << ",\t";

		const double EPS = 1e-9;		/* 误差精度: [-EPS,EPS] 区间内视为 0 */
		if (time1 - time2 > EPS)	  cout << "Nice : 0.618" << endl;
		else if (time1 - time2 < -EPS)	cout << "Nice : 0.5" << endl;
		else 	cout << "Time equality,Nice : 0.618 and 0.5" << endl;
	}

	return 0;
}

  • 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
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143

测试结果：

// 测试结果
// 以下为每组数据为 规模为10万的数组，进行100次二分查询所用时间（单位：微秒级）
// 这里共有十组测试数据
0.5：    用时 1.2e-06
0.618：  用时 8e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 1.3e-06
0.618：  用时 8e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 1.5e-06
0.618：  用时 5e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 5e-07
0.618：  用时 6e-07
匹配失败次数  0,        Nice : 0.5
0.5：    用时 1.2e-06
0.618：  用时 1e-06
匹配失败次数  0,        Nice : 0.618
0.5：    用时 1.4e-06
0.618：  用时 6e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 5e-07
0.618：  用时 2e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 1.2e-06
0.618：  用时 6e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 1e-06
0.618：  用时 5e-07
匹配失败次数  0,        Nice : 0.618
0.5：    用时 1.5e-06
0.618：  用时 7e-07
匹配失败次数  0,        Nice : 0.618

// 扩展，浮点数在计算机中存储使用IEEE 754标准，表示形式为'符号位'+'阶码'+'尾数'
// 注：其中 1e-9 表示浮点数 0.000000001 
// 如：
0.000000001		根据IEE754标椎，其二进制表示为:
00110000100010010111000001011111
-0.000000001	二进制表示为:
10110000100010010111000001011111

  • 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
  • 37
  • 38
  • 39
  • 40
  • 41

最终结果显示，在大部分情况下找黄金分割点的方法确实要优于等分查找的方法。因此，我们可以通过找黄金分割点的方法优化 mid 折半步骤，从而达到优化二分查询的目的 。

黄金分割算法参考文献：
[1]邹永林,唐晓阳.黄金分割算法与顺序表查找[J].福建电脑,2002(02):16-17.
华罗庚的优选法参考博文：漫谈斐波那契数列与黄金分割比

最后，如果觉得我的文章对你有帮助的话请帮忙点个赞，你的鼓励就是我学习的动力。如果文章中有错误的地方欢迎指正，有不同意见的同学也欢迎在评论区留言，互相学习。

——学习路上，你我共勉
记录几点关于随机数与计时函数的笔记

主要是关于最后的黄金分割点与二分法实现的二分查询效率测试，在编写测试代码时，出了一点小问题。是关于随机数与计时器的一些知识，最后只能求助于网络（学艺不精，惭愧惭愧）。

关于随机数：

  • 引用自C 库函数 - srand()：
    srand((unsigned)time(NULL)) 详解
    srand 函数是随机数发生器的初始化函数。
    原型:void srand(unsigned seed);
    用法: 它初始化随机种子，会提供一个种子，这个种子会对应一个随机数，如果使用相同的种子后面的 rand() 函数会出现一样的随机数，如: srand(1); 直接使用 1 来初始化种子。不过为了防止随机数每次重复，常常使用系统时间来初始化，即使用 time函数来获得系统时间，它的返回值为从 00:00:00 GMT, January 1, 1970 到现在所持续的秒数，然后将time_t型数据转化为(unsigned)型再传给srand函数，即: srand((unsigned) time(&t)); 还有一个经常用法，不需要定义time_t型t变量,即: srand((unsigned) time(NULL)); 直接传入一个空指针，因为你的程序中往往并不需要经过参数获得的数据。
    进一步说明下：计算机并不能产生真正的随机数，而是已经编写好的一些无规则排列的数字存储在电脑里，把这些数字划分为若干相等的N份，并为每份加上一个编号用srand()函数获取这个编号，然后rand()就按顺序获取这些数字，当srand()的参数值固定的时候，rand()获得的数也是固定的，所以一般srand的参数用time(NULL)，因为系统的时间一直在变，所以rand()获得的数，也就一直在变，相当于是随机数了。只要用户或第三方不设置随机种子，那么在默认情况下随机种子来自系统时钟。如果想在一个程序中生成随机数序列，需要至多在生成随机数之前设置一次随机种子。”
  • 参考自关于rand()和srand()：
    使用 srand((unsigned) time(NULL)) 初始化的随机种子，在1s间隔内随机种子可视为不变，因此生成的随机数可能相同。
  • 参考自 随机数—秒及毫秒级随机数种子（C++）
	//srand((unsigned)time(NULL));	// 秒级种子
	
	timeb tm;
	ftime(&tm);
	srand(tm.millitm);				// 毫秒级种子

  • 1
  • 2
  • 3
  • 4
  • 5

关于计时器

由于之前一直在使用 clock() 函数做函数运行时间的测试，并且也没有翻过车。clock() 使用非常方便，在待测函数前通过一个 size_t 类型（无符号整型 unsigned int）的整型数据接受 clock() 当前返回的时间，在待测函数后再次使用一个 size_t 类型的整型数据接受 clock() 的返回的时间，两者做差即可得出运行时间（单位：处理器时钟所使用的时间）。

   size_t start_t = clock();
   func();		// 待测函数
   size_t end_t = clock();
   cout << "CPU 占用的总时间：" << (double)(end_t - start_t) / CLOCKS_PER_SEC << endl;

  • 1
  • 2
  • 3
  • 4
#include<windows.h>  
int main()
{
	LARGE_INTEGER nFreq;
	LARGE_INTEGER nBeginTime;
	LARGE_INTEGER nEndTime;
	QueryPerformanceFrequency(&nFreq);
	QueryPerformanceCounter(&nBeginTime);//开始计时  
	func()		// 待测函数
	QueryPerformanceCounter(&nEndTime);//停止计时  
	time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;//计算程序执行时间单位为s  
	cout << "运行时间：" << time * 1000 << "ms" << endl;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/230496
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号