1 条题解
-
0
#include <bits/stdc++.h> using namespace std; // 全局数组:arr存储有序原数组,arr1存储待查询的数值 int arr[100100], arr1[100100]; // [1] 二分查找函数:在有序数组arr[0..b-1]中,查找值a第一次出现的1-based位置 // 找到则返回位置,否则返回-1 int f(int a, int b){ int l = 0, r = b; // 二分边界:左闭右开区间 [l, r) while(l < r){ int mid = (l + r) / 2; if(arr[mid] > a){ r = mid; // 目标值在左半区间 }else if(arr[mid] < a){ l = mid + 1; // 目标值在右半区间 }else{ r = mid; // 找到a,继续向左找第一个出现的位置 } } // 循环结束后l=r,检查该位置是否等于a if(arr[l] == a) return l + 1; // 转换为1-based位置 return -1; // 未找到返回-1 } int main(){ int n; // [2] 原数组的元素个数 cin >> n; // [3] 输入有序原数组 for(int i = 0; i < n; i++) cin >> arr[i]; int a; // [4] 待查询的数值个数 cin >> a; // [5] 输入所有待查询的数值 for(int i = 0; i < a; i++){ cin >> arr1[i]; } // [6] 遍历每个查询值,调用二分函数并输出结果 for(int i = 0; i < a; i++){ cout << f(arr1[i], n) << " "; } return 0; }
- 1
信息
- ID
- 1215
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者