修改折半查找算法使之能够进行范围查找的C语言代码
时间: 2024-05-09 21:19:53 浏览: 6
以下是修改后的折半查找算法,支持范围查找:
```c
#include <stdio.h>
// 二分查找(折半查找)函数,返回下标
int binarySearch(int arr[], int left, int right, int target) {
// 当左指针小于等于右指针时,继续查找
while (left <= right) {
int mid = left + (right - left) / 2; // 中间位置
if (arr[mid] == target) { // 找到目标值,返回下标
return mid;
} else if (arr[mid] < target) { // 目标值在右半部分,继续查找右半部分
left = mid + 1;
} else { // 目标值在左半部分,继续查找左半部分
right = mid - 1;
}
}
return -1; // 没有找到目标值,返回-1
}
// 范围查找函数,返回符合条件的元素个数
int rangeSearch(int arr[], int n, int left, int right, int min, int max, int result[]) {
int count = 0; // 符合条件的元素个数
int i = binarySearch(arr, left, right, min); // 查找左边界
if (i == -1) { // 没有找到左边界,直接返回
return count;
}
while (i <= right && arr[i] <= max) { // 查找符合条件的元素
result[count++] = arr[i++];
}
return count; // 返回符合条件的元素个数
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int result[n]; // 存储符合条件的元素
int count = rangeSearch(arr, n, 0, n - 1, 5, 15, result); // 查找范围为[5, 15]的元素
printf("符合条件的元素个数为:%d\n", count);
printf("符合条件的元素为:");
for (int i = 0; i < count; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}
```
在上述代码中,`rangeSearch`函数接收一个数组、数组长度、左右边界、范围最小值和最大值以及一个存储符合条件的元素的数组。在函数内部,先使用二分查找算法找到范围的左边界,然后依次向右遍历查找符合条件的元素,直到超出范围或者到达数组右边界。函数返回符合条件的元素个数。在`main`函数中,调用`rangeSearch`函数查找范围为[5, 15]的元素,并输出结果。