随机产生80个整数构成的递增序列,使用折半查找算法查找指定的整数,并统计比较次数。提示:可用 a[i] = a[i-1] + rand() % 10 + 1产生递增序列。C语言实现
时间: 2024-01-22 19:20:56 浏览: 24
以下是使用折半查找算法查找指定的整数并统计比较次数的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 80
int binary_search(int arr[], int n, int key, int *count)
{
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
(*count)++;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main()
{
int a[SIZE];
int i, key, pos, count = 0;
srand(time(NULL));
a[0] = rand() % 10 + 1;
for (i = 1; i < SIZE; i++) {
a[i] = a[i-1] + rand() % 10 + 1;
}
printf("请输入要查找的整数:\n");
scanf("%d", &key);
pos = binary_search(a, SIZE, key, &count);
if (pos == -1) {
printf("未找到该整数!\n");
} else {
printf("已找到该整数,位置为:%d\n", pos);
}
printf("比较次数为:%d\n", count);
return 0;
}
```
运行程序,输入要查找的整数,即可输出查找结果和比较次数。