C语言编写两路比较的折半查找程序,并对随机生成的包含1000000个元素的有序列表进行成功查找
时间: 2024-10-13 20:10:36 浏览: 2
在C语言中,我们可以编写一个二分查找算法(也称为折半查找)用于在一个已排序数组中查找特定元素。这个算法基于这样的原理:每次将搜索区间缩小一半,直到找到目标值或者区间为空。以下是基本的C代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 二分查找函数
int binarySearch(int arr[], int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
// 如果中间元素正好是我们要找的
if (arr[mid] == target)
return mid;
// 如果中间元素比目标小,我们继续在左半部分查找
else if (arr[mid] < target)
return binarySearch(arr, mid + 1, right, target);
// 否则我们在右半部分查找
else
return binarySearch(arr, left, mid - 1, target);
}
// 如果区间为空,说明目标不存在于数组中
return -1;
}
int main() {
srand(time(0)); // 设置随机种子以便生成随机数
int n = 1000000; // 数组大小
int *sortedArray = malloc(n * sizeof(int));
// 随机填充数组
for (int i = 0; i < n; ++i) {
sortedArray[i] = rand() % n;
printf("Element at index %d: %d\n", i, sortedArray[i]);
}
// 对数组进行排序(这里假设已经排序完成)
// ... (排序过程略)
int target = rand() % n; // 生成一个随机的目标值
int result = binarySearch(sortedArray, 0, n - 1, target);
if (result != -1) {
printf("Target found at index %d\n", result);
} else {
printf("Target not found in the array.\n");
}
free(sortedArray); // 释放内存
return 0;
}
```