用C++语言编写：输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 输入格式: 输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。 输出格式: 输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 输入样例: 4 1 2 3 4 1 输出样例: 0 2

以下是使用C++实现的二分查找算法，可以直接复制运行：

#include <iostream>
using namespace std;

int main() {
int n, x;
cin >> n;
int nums[n]; // 用数组存储n个整数
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
cin >> x;

int left = 0, right = n - 1, count = 0;
while (left <= right) {
int mid = (left + right) / 2;
count++;
if (nums[mid] == x) {
cout << mid << " " << count << endl;
return 0;
} else if (nums[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}

cout << -1 << " " << count << endl;
return 0;
}

相关问题

键盘上任意顺序输入15个整型数据，将数组元素按降序排列。再读入一个整数m ,使用折半查找方法，查找m是否在数组中。若在，输出其位置；若不在，输出“no"。

要完成这个任务，可以使用C++编写一个程序，首先接收15个整数并将它们放入数组，然后对数组进行降序排序，最后使用折半查找算法找到指定值的位置。以下是完整的代码实现：

#include <iostream>
#include <vector>
using namespace std;

// 升序比较函数，用于sort函数
bool compare(int a, int b) {
    return a > b;
}

void insertAndSort(vector<int>& arr, int n) {
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        arr.push_back(num);
    }
    sort(arr.begin(), arr.end(), compare); // 对数组进行降序排序
}

int binarySearch(vector<int>& arr, int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binarySearch(arr, target, low, mid - 1);
    else
        return binarySearch(arr, target, mid + 1, high);
}

int main() {
    vector<int> arr(15);
    insertAndSort(arr, 15);

    int m;
    cout << "Enter the value to search: ";
    cin >> m;

    int result = binarySearch(arr, m, 0, arr.size() - 1);

    if (result != -1)
        cout << "Value found at position " << result + 1 << endl;
    else
        cout << "no" << endl;

    return 0;
}

在这个程序中，我们先创建了一个大小为15的整数向量`arr`，然后通过循环接收用户的输入并插入到数组中。接着，我们使用`compare`函数作为`sort`的第三个参数，使得数组按照降序排列。然后，用户输入一个值`m`，我们调用`binarySearch`函数进行查找，如果找到了则输出位置，否则输出"No"。