有15个数按由大到小顺序存放在一个数组中,有arr[15]={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值,如果不在该数组中,则输出"无此数"。
时间: 2024-12-04 21:29:34 浏览: 16
折半查找法(Binary Search),也称为二分查找,是一种非常高效的搜索算法,适用于已排序的数据集合。在这种情况下,由于数组`arr[15]`已经按照降序排列,我们可以利用这个性质进行查找。
下面是使用C语言实现折半查找的方法:
```c
#include <stdio.h>
// 函数声明
int binary_search(int arr[], int low, int high, int target);
int main() {
int arr[15] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int target;
printf("请输入要查找的数:");
scanf("%d", &target);
// 如果数组长度为0或1,直接返回第一个元素的位置,否则执行二分查找
if (high == 0 || high == 1) {
if (arr[high] == target)
printf("找到了,位置:%d\n", high + 1);
else
printf("无此数\n");
} else {
int result = binary_search(arr, 0, high - 1, target);
if (result != -1)
printf("找到了,位置:%d\n", result + 1); // 注意索引从0开始计数
else
printf("无此数\n");
}
return 0;
}
// 二分查找函数
int binary_search(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2; // 计算中间位置
if (arr[mid] == target) {
// 找到了目标值,但需要检查左侧是否有相同元素,避免重复索引
while (mid > 0 && arr[mid - 1] == target)
mid--;
return mid;
} else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
// 没找到目标值,返回-1表示不存在
return -1;
}
```
在这个程序中,`binary_search`函数接收数组、起始下标(low)、结束下标(high)以及目标值。它会在每次迭代时将搜索范围缩小一半,直到找到目标值或者搜索范围为空(即low > high)。如果没有找到目标值,函数返回-1。
阅读全文