数据结构查找技术，顺序查找，折半查找代码解疑

Question

有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();      //记录查找算法的结束时间
……
}

Answer 1

折半查找需要先对数组排序才行。排序的时间是否算在里面呢？代码如下：

#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;
}