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

輸出

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 提供了優秀的排序和搜尋方法，這幫助我們在不過度思考實現的情況下編寫了該問題的程式碼。

更新於: 2022年8月10日

343 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告