有15个数按由大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则输出“无此数”。
时间: 2023-04-28 20:02:29 浏览: 247
折半查找法,也叫二分查找法,是一种高效的查找算法。它的基本思想是将有序数组分成两部分,取中间位置的数与要查找的数进行比较,如果相等,则查找成功;如果要查找的数比中间位置的数小,则在左半部分继续查找;如果要查找的数比中间位置的数大,则在右半部分继续查找。不断重复这个过程,直到找到要查找的数或者确定该数不存在为止。
对于本题,我们可以先将给定的数组按照从大到小的顺序进行排序,然后再使用折半查找法进行查找。具体步骤如下:
1. 将给定的数组按照从大到小的顺序进行排序。
2. 输入要查找的数。
3. 定义左右两个指针,分别指向数组的第一个元素和最后一个元素。
4. 在循环中,计算中间位置的下标,然后将要查找的数与中间位置的数进行比较。
5. 如果相等,则查找成功,输出该数在数组中的位置。
6. 如果要查找的数比中间位置的数小,则在左半部分继续查找,将右指针移动到中间位置的左边一位。
7. 如果要查找的数比中间位置的数大,则在右半部分继续查找,将左指针移动到中间位置的右边一位。
8. 不断重复步骤4-7,直到找到要查找的数或者确定该数不存在为止。
9. 如果最终没有找到要查找的数,则输出“无此数”。
下面是示例代码:
```
#include <stdio.h>
int main()
{
int a[15] = {23, 19, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; // 给定的数组
int n = 15; // 数组的长度
int x; // 要查找的数
int left = , right = n - 1; // 左右指针
// 对数组进行排序(从大到小)
for (int i = ; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] < a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
// 输入要查找的数
printf("请输入要查找的数:");
scanf("%d", &x);
// 折半查找
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == x) {
printf("%d是数组中第%d个元素的值。\n", x, mid + 1);
return ;
} else if (a[mid] > x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 如果最终没有找到要查找的数,则输出“无此数”
printf("无此数。\n");
return ;
}
```
阅读全文