在本文中，我們給出了一個(gè)整數(shù)數(shù)組和一個(gè)關(guān)鍵字。我們需要在數(shù)組中重復(fù)查找關(guān)鍵字，并在每次查找時(shí)將其加倍。我們需要返回在進(jìn)行這個(gè)操作時(shí)數(shù)組中不存在的值。
查看一些輸入場(chǎng)景以了解該方法在不同情況下的工作原理
讓我們來看一個(gè)數(shù)組 [1,2,6,3,7,4,9]，它的鍵是 1。
Input: {1, 2, 3, 4, 5, 6}, k = 1
Result: 8
登錄后復(fù)制
如果我們找到 1，我們會(huì)將其加倍為 2。
如果我們找到2，我們會(huì)把它加倍變成4。
如果我們找到4，我們將其加倍為8。
我們返回 8，因?yàn)閿?shù)組中沒有元素 8
在另一種情況下，我們考慮一個(gè)數(shù)組 {2, 3, 7, 8, 5, 9}，它的鍵是 1。
Input: {2, 3, 7, 8, 5, 9}, k = 1
Result: 1
登錄后復(fù)制
我們按原樣返回 1，因?yàn)檩斎霐?shù)組中沒有元素 1。
算法
對(duì)數(shù)組元素進(jìn)行排序，因?yàn)閷?duì)于小型數(shù)組來說，執(zhí)行二分搜索的復(fù)雜度較低。
每當(dāng)數(shù)組中的元素與鍵值匹配時(shí)，將鍵值加倍，并再次搜索數(shù)組以找到與新鍵匹配的元素。
重復(fù)此步驟，直到數(shù)組中沒有與雙倍鍵值匹配的元素為止。
最終的鍵值就是得到的輸出。
示例（使用向量ADT）
我們通過對(duì)數(shù)組進(jìn)行排序來開始實(shí)現(xiàn)此方法。之后，我們將完全按照問題所說的去做；搜索并加倍。我們通過二分搜索來進(jìn)行優(yōu)化搜索。讓我們通過應(yīng)用相同的邏輯來看看 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;
}
登錄后復(fù)制
輸出
8
登錄后復(fù)制
示例（不使用向量 ADT）
C++ 程序也遵循相同的邏輯，但不使用向量抽象數(shù)據(jù)類型。
我們通過對(duì)數(shù)組進(jìn)行排序來開始實(shí)施這種方法。之后，我們將按照問題要求進(jìn)行操作；搜索并加倍。我們通過二分搜索進(jìn)行優(yōu)化。
#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;
}
登錄后復(fù)制
輸出
12
登錄后復(fù)制
結(jié)論
我們使用了STL二分查找方法，根據(jù)是否找到元素返回true或false。我們還可以使用我們自定義的二分搜索實(shí)現(xiàn)。 STL提供了優(yōu)秀的排序和搜索方法，這幫助我們?cè)诰帉憜栴}時(shí)無需過度思考實(shí)現(xiàn)。
以上就是使用C++，通過每次成功搜索后將元素加倍來重復(fù)搜索一個(gè)元素的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章！
