用c++ 编程实现:按降序输入若干个整数并存入一个整型数组中,对从键盘输入的数据进行查找,要求使用折半查找算法,输出查找结果,并统计本轮折半查找的次数。(要求:循环实现多个数的折半查找,输入1则继续下一个数的查找、输入其他整数则结束查找)。
时间: 2024-05-08 22:18:44 浏览: 13
好的,我已经记录下你的问题了。以下是代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
int binary_search(int arr[], int len, int target, int& count) {
int left = 0, right = len - 1;
while (left <= right) {
count++;
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
void descending_sort(int arr[], int len) {
sort(arr, arr + len);
reverse(arr, arr + len);
}
int main() {
int arr[100], len = 0, count = 0;
cout << "请输入要查找的整数,以-1结束输入:" << endl;
int num;
cin >> num;
while (num != -1) {
arr[len++] = num;
cin >> num;
}
descending_sort(arr, len);
while (true) {
cout << "请输入要查找的整数:" << endl;
int target;
cin >> target;
count = 0;
int res = binary_search(arr, len, target, count);
if (res == -1) {
cout << "未找到该整数!本轮查找次数:" << count << endl;
} else {
cout << "找到该整数,位置为:" << res << ",本轮查找次数:" << count << endl;
}
cout << "输入1以继续查找,其他整数结束查找:" << endl;
cin >> num;
if (num != 1) {
break;
}
}
return 0;
}
```
这段代码会先让你输入一些整数,以-1结束输入,然后对这些整数按降序排序,再进行折半查找。程序会循环实现多个数的折半查找,每轮查找都会统计查找次数,并提供继续查找的选项(输入1继续查找,其他整数结束查找)。请注意,这段代码所用的查找算法只适用于已经按降序排序的数组。