有A和B两个数组，A数组中存储500个2000以内的随机整数，B数组中存储10个2000以内的随机整数，完成以下操作:
（1）用顺序查找算法显示B数组中每个元素在A数组中的位置，并返回该算法所用时间；
（2）用折半查找算法显示B数组中每个元素在A数组中的位置，并返回该算法所用时间；
部分参考代码如下：
#include<ctime> //使用函数库ctime
……
int main()
{
clock_t start,finish; //定义查找开始时间和结束时间变量
……
start=clock(); //记录查找算法的开始时间
查找算法
finish=clock(); //记录查找算法的结束时间
……
}
折半查找需要先对数组排序才行。排序的时间是否算在里面呢？代码如下：
#include <iostream>
#include <ctime>
using namespace std;
//冒泡排序
void bubblesort(int a[], int n)
{
int i, j, t;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}
//顺序查找
int SxSearch(int a[], int x, int n)
{
int i;
for (i = 0; i < n; i++)
{
if (a[i] == x)
return i;
}
return -1;
}
//数组以升序排列时，折半查找查找x
int binSearch(int a[], int x, int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (x < a[mid])
high = mid - 1;
else if (x > a[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
int main()
{
clock_t start, finish;
int a[500], b[10];
int i, j;
int index;
//生成随机数
srand((unsigned int)time(0));
for (i = 0; i < 500; i++)
a[i] = rand() % 2000; //生成2000以内的随机数
for (i = 0; i < 10; i++)
b[i] = rand() % 2000;
//顺序查找
start = clock();
for (i = 0; i < 10; i++)
{
index = SxSearch(a, b[i], 500);
}
finish = clock();
cout << "顺序查找时间：" << finish - start << endl;
//折半查找
start = clock();
bubblesort(a, 500);
for (i = 0; i < 10; i++)
{
index = binSearch(a, b[i], 500);
}
finish = clock();
cout << "折半查找时间（含排序时间）：" << finish - start << endl;
return 0;
}