有12个数{4,5,8,10,78,79,80,82,86,88,90,92}按由小到大顺序存放在一个数组中a,从键盘输入一个数,要求用折半查找法找出该数是数组中第几个元素的值(从0开始)。如果该数不在数组中,则输出“无此数”。
时间: 2023-07-27 09:18:26 浏览: 182
习题|Python100道练习题,建议收藏.docx
好的,这个问题可以用折半查找法来解决。
首先,我们需要将数组a按照从小到大的顺序排序。可以使用C++标准库中的sort函数来实现:
```cpp
#include <algorithm>
using namespace std;
int a[12] = {4,5,8,10,78,79,80,82,86,88,90,92};
sort(a, a+12); // 排序
```
然后,我们需要从键盘输入一个数,可以使用C++标准库中的cin函数来实现:
```cpp
int x;
cin >> x;
```
接着,我们可以使用折半查找法来查找该数在数组中的位置。折半查找法的基本思想是:将数组分成两个部分,如果要查找的数比中间数小,则在左半部分继续查找;如果要查找的数比中间数大,则在右半部分继续查找;如果要查找的数正好等于中间数,则查找成功。
代码实现如下:
```cpp
int low = 0, high = 11;
while (low <= high) {
int mid = (low + high) / 2;
if (x < a[mid]) {
high = mid - 1;
} else if (x > a[mid]) {
low = mid + 1;
} else {
cout << "该数是数组中第" << mid << "个元素的值。" << endl;
return 0;
}
}
cout << "无此数" << endl;
```
完整代码如下:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[12] = {4,5,8,10,78,79,80,82,86,88,90,92};
sort(a, a+12); // 排序
int x;
cin >> x;
int low = 0, high = 11;
while (low <= high) {
int mid = (low + high) / 2;
if (x < a[mid]) {
high = mid - 1;
} else if (x > a[mid]) {
low = mid + 1;
} else {
cout << "该数是数组中第" << mid << "个元素的值。" << endl;
return 0;
}
}
cout << "无此数" << endl;
return 0;
}
```
阅读全文