使用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。

演算法

• 對陣列元素進行排序，因為對於小型陣列來說，執行二分搜尋的複雜度較低。

• 每當陣列中的元素與鍵值相符時，將鍵值加倍，並再次搜尋陣列以找到與新鍵相符的元素。

• 重複此步驟，直到陣列中沒有與雙倍鍵值相符的元素為止。

• 最終的鍵值就是得到的輸出。

範例（使用向量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;
}

輸出

8

範例（不使用向量 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;
}

輸出

12

結論

我們使用了STL二分查找方法，根據是否找到元素傳回true或false。我們還可以使用我們自訂的二分搜尋實作。 STL提供了優秀的排序和搜尋方法，這幫助我們在編寫問題時無需過度思考實作。

以上是使用C++，透過每次成功搜尋後將元素加倍來重複搜尋一個元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！