折半查找需要先对数组排序才行。排序的时间是否算在里面呢?代码如下:
#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;
}