使用C++，通过每次成功搜索后将元素加倍来重复搜索一个元素

WBOY 转载: 2023-09-25 20:09:11 538浏览

在本文中，我们给出了一个整数数组和一个关键字。我们需要在数组中重复查找关键字，并在每次查找时将其加倍。我们需要返回在进行这个操作时数组中不存在的值。

查看一些输入场景以了解该方法在不同情况下的工作原理

让我们来看一个数组 [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。

算法

对数组元素进行排序，因为对于小型数组来说，执行二分搜索的复杂度较低。
每当数组中的元素与键值匹配时，将键值加倍，并再次搜索数组以找到与新键匹配的元素。
重复此步骤，直到数组中没有与双倍键值匹配的元素为止。
最终的键值就是得到的输出。

示例（使用向量ADT）

我们通过对数组进行排序来开始实现此方法。之后，我们将完全按照问题所说的去做；搜索并加倍。我们通过二分搜索来进行优化搜索。让我们通过应用相同的逻辑来看看 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;
}

输出

示例（不使用向量 ADT）

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;
}