Menggunakan C++, berulang kali mencari elemen dengan menggandakan elemen selepas setiap carian yang berjaya

Dalam artikel ini, kami diberikan tatasusunan integer dan kata kunci. Kita perlu berulang kali mencari kunci dalam tatasusunan, menggandakannya dengan setiap carian. Kita perlu mengembalikan nilai yang tidak terdapat dalam tatasusunan pada masa melakukan operasi ini.

Lihat beberapa senario input untuk melihat cara kaedah berfungsi dalam situasi yang berbeza

Mari kita lihat tatasusunan [1,2,6,3,7,4,9] yang kuncinya ialah 1.

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

Jika kita jumpa 1, kita gandakan kepada 2.

Jika kita jumpa 2, kita gandakan menjadi 4.

Jika kita jumpa 4, kita gandakan kepada 8.

Kami mengembalikan 8 kerana tiada unsur 8 dalam tatasusunan

Dalam kes lain, kami mempertimbangkan tatasusunan {2, 3, 7, 8, 5, 9}, yang kuncinya ialah 1.

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

Kami mengembalikan 1 sebagaimana adanya kerana tiada unsur 1 dalam tatasusunan input.

Algoritma

• Isih elemen tatasusunan kerana melakukan carian binari adalah kurang kompleks untuk tatasusunan kecil.

• Setiap kali elemen dalam tatasusunan sepadan dengan nilai kunci, gandakan nilai kunci dan cari tatasusunan sekali lagi untuk mencari elemen yang sepadan dengan kunci baharu.

• Ulang langkah ini sehingga tiada unsur yang sepadan dengan nilai kunci berganda dalam tatasusunan.

• Nilai kunci terakhir ialah output yang diperolehi.

Contoh (menggunakan vektor ADT)

Kami mula melaksanakan kaedah ini dengan mengisih tatasusunan. Selepas itu, kami akan melakukan apa yang dikatakan oleh soalan itu dan menggandakan. Kami melakukan carian yang dioptimumkan melalui carian binari. Mari lihat program C++ dengan menggunakan logik yang sama -

#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

Contoh (tidak menggunakan vektor ADT)

C++ juga mengikut logik yang sama tetapi tidak menggunakan jenis data abstrak vektor.

Kami mula melaksanakan pendekatan ini dengan mengisih tatasusunan. Selepas itu kami akan melakukan apa yang diminta oleh soalan; Kami mengoptimumkan melalui carian binari.

#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

KESIMPULAN

Kami menggunakan kaedah carian binari STL untuk mengembalikan benar atau salah bergantung pada sama ada elemen ditemui. Kami juga boleh menggunakan pelaksanaan carian binari tersuai kami. STL menyediakan kaedah pengisihan dan carian yang sangat baik, yang membantu kami menulis masalah tanpa terlalu memikirkan pelaksanaannya.

Atas ialah kandungan terperinci Menggunakan C++, berulang kali mencari elemen dengan menggandakan elemen selepas setiap carian yang berjaya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!