数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 重复搜索元素，每次成功搜索后将其加倍
在本文中，我们给定一个整数数组和一个键值。我们必须在数组中重复查找该键值，并在每次找到该键值时将其加倍。我们需要返回在此操作中数组中不存在的值。
一些输入场景，可以帮助理解该方法在不同情况下的工作原理
假设我们有一个数组 [1,2,6,3,7,4,9]，其键值是 1。
Input: {1, 2, 3, 4, 5, 6}, k = 1
Result: 8
如果我们找到 1，则将其加倍为 2。
如果我们找到 2，则将其加倍为 4。
如果我们找到 4，则将其加倍为 8。
我们返回 8，因为数组中没有元素 8
在另一种情况下，让我们考虑一个数组 {2, 3, 7, 8, 5, 9}，其键值是 1。
Input: {2, 3, 7, 8, 5, 9}, k = 1
Result: 1
我们返回 1 本身，因为输入数组中没有元素 1。
算法
对数组元素进行排序，因为对于小数组来说，执行二分查找的复杂度较低。
每当数组中的元素与键值匹配时，将键值加倍，并再次搜索数组以查找与新键值匹配的元素。
重复此步骤，直到数组中没有元素与加倍后的键值匹配。
最终的键值即为获得的输出。
示例（使用向量抽象数据类型）
我们首先通过对数组进行排序来实现此方法。之后，我们将按照题目要求执行操作：搜索和加倍。为了优化，我们使用二分查找进行搜索。让我们看一下应用相同逻辑的 C++ 程序：
#include <iostream> #include <algorithm> #include <vector> using namespace std; int solve(vector<int>& arr, int key) { sort(arr.begin(), arr.end()); bool found = binary_search(arr.begin(), arr.end(), key); while(found) { key*=2; found = binary_search(arr.begin(), arr.end(), key); } return key; } int main() { vector<int> arr = {1,2,6,3,7,4,9}; int key = 1; cout << solve(arr, key) << endl; return 0; }
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
8
示例（不使用向量抽象数据类型）
C++ 程序也遵循相同的逻辑，但不使用向量抽象数据类型。
我们首先通过对数组进行排序来实现此方法。之后，我们将按照题目要求执行操作：搜索和加倍。为了优化，我们使用二分查找进行搜索。
#include <bits/stdc++.h> using namespace std; int SearchElement(int arr[], int n, int k) { // Sorting is done so binary searching in the element // would be easier sort(arr, arr + n); int max = arr[n - 1]; // Declaring the maximum element in the array while (k < max) { // search for the element k in the array if (binary_search(arr, arr + n, k)) k *= 2; else return k; } return k; } int main() { int arr[] = {1,2,6,3,7,4,9}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; cout << SearchElement(arr, n, k); return 0; }
输出
12
结论
我们使用了 STL 二分查找方法，该方法根据元素是否找到返回真或假。我们也可以使用自定义的二分查找实现。STL 提供了优秀的排序和搜索方法，这帮助我们在不过度思考实现的情况下编写了该问题的代码。
343 次浏览
