C++ 程序用于在数组中搜索特定值
c++server side programmingprogramming
假设我们给定一个包含 n 个排序整数值的数组"arr"。我们还给定一个大小为 q 的数组"query"，我们必须判断"query"中的值是否存在于给定数组"arr"中。如果 query 中的值存在于 arr 中，我们将打印"Present"以及该值所在的位置。否则，我们将打印"Not present"并打印 arr 中大于 query 中的值的最小值所在的位置。我们必须记住数组是从 1 开始索引的。
因此，如果输入为 n = 8, arr = {1, 2, 3, 4, 7, 9, 12, 15} , q = 3, query = {1, 5, 8}，则输出将是
Present 1 Not present 5 Not present 6
querys 的第一个值存在于 arr 中的位置 1。
querys 的第二个值不存在于 arr 中。最小值大于查询值的位置是 5。
同样，querys 的第三个值也不存在于 arr 中。大于它的值位于 arr 的第 6 位。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个数组值
- 初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
- 在 values 的末尾插入 arr[i]
- 初始化 i := 0，当 i < q 时，更新(将 i 增加 1)，执行 −
- idx := (values 中第一个不小于 query[i] 的元素的位置) - values 中第一个元素的位置
- 如果 values[idx] 与 query[i] 相同，则 −
- print("Present ")
- Otherwise,
- print("Not present ")
- print(idx + 1)
示例
让我们看看下面的实现以便更好地理解 −
#include <vector>
#include <iostream>
using namespace std;
void solve(int n, int arr[], int q, int query[]) {
vector<int> values;
for(int i = 0; i < n; i++){
values.push_back(arr[i]);
}
for(int i = 0; i < q; i++) {
int idx = lower_bound (values.begin(), values.end(),
query[i]) - values.begin();
if (values[idx] == query[i])
cout << "Present ";
else
cout << "Not present ";
cout << idx + 1 << endl;
}
}
int main() {
int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15};
int query_arr[] = {1, 5, 8};
solve(8, input_arr, 3, query_arr);
return 0;
}
输入(stdin)
int input_arr[] = {1, 2, 3, 4, 7, 9, 12, 15};
int query_arr[] = {1, 5, 8};
solve(8, input_arr, 3, query_arr);
输出
Present 1 Not present 5 Not present 6
