C++ 二分查找，数组找数，无法AC，修改后依然无法AC，请指教，悬赏，求AC代码~
【题目描述】
给定一个已经从小到大排好序的数组，数组内有n个元素。现在，你需要在数组中查找元素x，如果x存在，输出它在数组中的位置（如果数组中有多个x，输出位置最小的一个），如果不存在，输出“no”。
【输入格式】
输入包括多行：
第一行包含一个整数n（1<=n<107）；
第二行输入n个整数(每个数不会超过107)；
第三行输入一个整数k（1<=k<=1000），表示需要进行k次查找；
接下来输入k行，每行输入一个整数x(每个数不会超过107)
【输出格式】
输出k行，对应每次查找的结果。
【输入样例】
6
1 2 2 2 3 4
3
2
5
3
【输出样例】
2
no
5
基于new bing修改后的编写：
#include <iostream>
using namespace std;
int binary_search(int arr[], int len, int target) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) { // 找到目标数了
while (mid > 0 && arr[mid - 1] == target) {//mid-1位置也是目标数，则在左半部分继续找
mid--;
}
return mid+1;
} else if (arr[mid] < target) { // 目标数在右半部分
left = mid + 1;
} else { // 目标数在左半部分
right = mid - 1;
}
}
return -1; // 没有找到目标数
}
int main() {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int k;
cin >> k;
int result[k];
for (int i = 0; i < k; i++) {
int x;
cin >> x;
result[i] = binary_search(arr, n, x);
}
for (int i = 0; i < k; i++) {
if (result[i] == -1) {
cout << "no\n";
} else {
cout << result[i] << endl;
}
}
return 0;
}
AC是什么？
答案参考ChapGPT Plus . 希望对你有帮助
下面是一个使用二分查找算法来解决这个问题的C++代码示例：
#include <iostream>
#include <vector>
using namespace std;
// 二分查找函数
int binarySearch(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // 继续向左边查找，寻找最小的位置
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
int result = binarySearch(arr, x);
if (result == -1) {
cout << "no" << endl;
} else {
cout << result + 1 << endl; // 注意位置从1开始计数
}
}
return 0;
}
你可以将该代码保存为.cpp文件，使用C++编译器进行编译运行。输入数组长度、数组元素、需要查找的次数以及每次查找的目标数值，然后输出对应的查找结果。
请注意，这里使用的是左闭右闭的二分查找方式，并且对于重复的目标数值，返回的是最左边的位置。同时，根据题目要求，输出位置时需要从1开始计数。
希望这个代码能够帮助你解决问题，如有其他疑问，请随时提问。
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 找到目标元素
while (mid > 0 && nums[mid - 1] == target) {
// 往左继续查找，找到位置最小的一个
mid--;
}
return mid;
} else if (nums[mid] < target) {
// 目标元素在右侧
left = mid + 1;
} else {
// 目标元素在左侧
right = mid - 1;
}
}
// 没找到目标元素
return -1;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int target;
cin >> target;
int result = binarySearch(nums, target);
if (result != -1) {
cout << result << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}
```
这里提供一个不用二分查找的做法，使用C++内置的哈希表（unordered_map）：
#include <cstdio>
#include <unordered_map>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
unordered_map<int, int> pos;
for(int i=1; i<=n; i++)
{
int x;
scanf("%d", &x);
pos.emplace(x, i);
}
int q;
scanf("%d", &q);
while(q--)
{
int x;
scanf("%d", &x);
auto it = pos.find(x);
if(it == pos.end())
puts("no");
else printf("%d\n", it->second);
}
return 0;
}
时间复杂度只有 O(n + k)，二分查找是 O(n + k log n)。
C++有自带的二分查找函数
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e7 + 5;
int n, k, x;
int a[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
scanf("%d", &k);
while (k--)
{
scanf("%d", &x);
int *p = lower_bound(a, a + n, x);
if (*p != x)
printf("no\n");
else
printf("%d\n", p - a + 1);
}
return 0;
}