Using C++, repeatedly search for an element by doubling the element after each successful search

In this article, we are given an array of integers and a keyword. We need to repeatedly look for the key in the array, doubling it with each lookup. We need to return a value that is not present in the array at the time of doing this operation.

Look at some input scenarios to see how the method works in different situations

Let's look at an array [1,2,6,3,7,4,9] whose key is 1.

Input: {1, 2, 3, 4, 5, 6}, k = 1
Result: 8

If we find 1, we double it to 2.

If we find 2, we double it to 4.

If we find 4, we double it to 8.

We return 8 because there is no element 8 in the array

In another case, we consider an array {2, 3, 7, 8, 5, 9} whose key is 1.

Input: {2, 3, 7, 8, 5, 9}, k = 1
Result: 1

We return 1 as is because there is no element 1 in the input array.

algorithm

• Sort the array elements because the complexity of performing a binary search is low for small arrays.

• Whenever an element in the array matches a key value, double the key value and search the array again to find an element matching the new key.

• Repeat this step until there are no elements matching the double key value in the array.

• The final key value is the output obtained.

Example (using vector ADT)

We start implementing this method by sorting the array. After that, we'll do exactly what the question says; search and double. We perform optimized search through binary search. Let us look at the C program by applying the same logic -

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

Output

8

Example (not using vector ADT)

C programs also follow the same logic but do not use the vector abstract data type.

We start implementing this approach by sorting the array. After that we'll do what the question asks for; search and double. We optimize via binary search.

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

Output

12

in conclusion

We used the STL binary search method to return true or false depending on whether the element is found. We can also use our custom binary search implementation. STL provides excellent sorting and searching methods, which help us write problems without overthinking the implementation.

The above is the detailed content of Using C++, repeatedly search for an element by doubling the element after each successful search. For more information, please follow other related articles on the PHP Chinese website!