二分查询也称折半查找（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;
}
示例2：有一个整型数组，如果数组有序，使用二分查询。
对于一个有序的数组，非常适合使用二分查找。二分查找思想为折半，如我们的猜数游戏。
模型如下：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|
- 如果我们选择从 “1” 位置作为查找的起始点，那么我们与1之间的距离为0，与10之间的距离为10，也就是说如果我们找1，那么只需一步就能找到，而我们要找10需要10步才能找到。最坏的情况下我们需要找10次。
- 如果我们选择从 “5”或“6” 位置作为查找起始点，那么我们与1和10之间的距离为5，并且如果我们查找的方式为每次取其中间位置的数跳跃式的查找，它在最好的情况在找一次，最坏的情况下只需要找3次。
事实上第二种的查找方式就用的是我们二分查找的思想，这仅仅是在1~10之间的查找范围，在某种程度上来说，查找范围越大，二分查找相对于普通的遍历查找优势就越明显。
时间复杂度：
由于二分查找每次取中位查找，对于规模为n的线性表来说，取值规律为： 。
分析：
- 第一次
- 第二次 ，其中，K表示取左半段或右半段
- 第三次 ，其中，K表示在第二次折半后，取左半段或右半段。
前三次查找模型大致如下：
| 0 | ||||||||
|---|---|---|---|---|---|---|---|---|
| 左顶点 | 第一次查找位置 | 右顶点 | ||||||
| 左顶点 | 第二次查找位置 | … … | 右顶点 | |||||
| 左顶点 | 第三次查找位置 | … … | … … | 右顶点 | ||||
| 左顶点 | 右顶点 |
- 第…次
- 第 m 次
在最坏的情况下，假设查找了 m 次，整个数组只剩下一个数据，那么可列等式：
或者
则：
因此最坏情况下的时间复杂度为：
下面是代码实现：
#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;
}
代码非常简单，但是你认为这样就完了吗？No NO No
如果在面试中面试官让你写一个二分查询，你写成这样的代码。那么很遗憾，回家等通知吧。
二分查询 | 面试官找茬，常见错误及代码的查漏补缺
这段二分查找代码说你写错吧，还不至于，可是说好吧，也还远远算不上。假如面试官针对你的代码找茬，你如和应对，如果没有天生机制过人的大脑和聪明才智的话，到时候就只能硬着头皮上了。好在现在还没有面试官对我们找茬，那我们就笨鸟先飞，先来个代码自省。俗话说的好，不打无把握的仗，“排除一切不可能后,剩下的就是真相”。同理，让我们将所有的问题都排查掉，让面试官无茬可找。下面让我们带入面试官的角色进行找茬，从不同角度分析这段代码。
找茬：
- 问题1：如果传入的参数是
ar == NULL或n < 1情况怎么办？
解决：if (NULL == ar || n < 1) return pos; - 问题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：如果数组不仅有序还含有重复值，要求 求出其第一个满足要求的下标或最后一个满足要求的下标。
解决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;
}
}
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;
}
递归：如果面试官此时又问，你能不能将此程序改为递归的方式求解 。
嗯，这个倒是不难，递归和循环的关系就像是两双胞胎，非常相似 。我们细心分析就会发现递归实际上也是一种循环，无非是自己调用自己罢了。下面就是二分查询的递归实现代码：
#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;
}
在解决了面试官的找茬后，面试官又问道，能不能尝试着优化一下呢 。什么？不会，那没事了，回去等通知吧。（开个玩笑）
以上代码基本上就是我们普通人的极限了，那么想要进阶，想要优化就只能靠它了。你问我他是谁？还能有谁，当然是我们算法的好基友数学了。
所以说，不想当数学家的程序猿，不是一个好的算法工程师。
二分查询 | 进阶：查询效率优化与黄金分割点 0.618
如表中所见，有 6 个数据，我们在寻找mid时采用的是 mid = left + (right - left + 1) / 2 的方法取中间值。
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| data | 1 | 2 | 3 | 4 | 5 | 6 |
对于 mid 等分的问题分析
其中，mid 的取值表达式也可以写成 mid = left + (right - left + 1) * 0.5 。在这段代码中，我们把 left - right 中的数值折半，或者叫等分，通过这种方式获得某段范围内的中间值。但是对于上表中的这 6 个数据而言，始终是无法等分的，在取中间值时要么最终取偏左的下标 2，要么取偏右的下标 3。
而我们常规的整除运算，取值一律偏左。如 2 除以 2 结果是1，3 除以 2 结果也是1 。而对于数组来说，下标都是从0开始的，也就是说对于长度为2的数组｛下标 0，1｝，，长度为3的数组 ｛下标 0，1，2｝， 。
对于本例来说 ，也是取的偏右的值，或者说下标偏大的值 。
总结：常规二分查找去中间值时采用的下标偏大原则，并不是真正意义上的等分。
左右边界查询效率的问题分析
那么，理论上对于偶数规模的问题而言，在查找右边的数据时会比查找左边的数据要快。比如对于一个有序数组 而言。查询最左边的 1，查询次数为 3 次，查询最右边的数据 6，查询次数为 2 次。具体查询过程见下表：
- 查询最左边的数据 1，下标为为0，即 ，下图仅显示下标，其中 分别表示第一次，第二次、第三次 mid 的位置。
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| i | |||||
| j | |||||
| k |
- 查询最右边的数据 6，下标为为5，即 ，下图仅显示下标，其中 分别表示第一次，第二次 mid 的位置。
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 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;
实践是检验真理的唯一标准，下面我们通过对规模为 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： 用时 " << time1 << endl;
cout << "0.618： 用时 " << time2 << endl;
cout << "匹配失败次数 " << inErr << ", ";
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;
}
测试结果：
// 测试结果
// 以下为每组数据为 规模为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
最终结果显示，在大部分情况下找黄金分割点的方法确实要优于等分查找的方法。因此，我们可以通过找黄金分割点的方法优化 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); // 毫秒级种子
关于计时器
由于之前一直在使用 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;
- 参考：C++测试代码的运行时间几种基本方法
这篇博客中介绍了一种高精度时控函数，可以返回微秒级的单位计时。具体使用方法如下：
#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;