Program C++ untuk mencari elemen dalam tatasusunan yang disusun dan diputar

Kami mendapat tatasusunan diisih diputarkan mengelilingi satu titik. Kami juga mendapat kunci untuk mencari dalam tatasusunan. Logik yang digunakan untuk mencari elemen dalam tatasusunan berputar ini ialah -

• Pertama, kita mencari elemen tengah tatasusunan. Jika kunci wujud, kami kembalikan bahawa kunci itu wujud dalam tatasusunan.

• Jika kunci tiada di tengah, kita boleh lihat jika bahagian kiri tatasusunan (dari kiri ke tengah) diisih. Jika disusun, anda boleh mencari kunci di sebelah kiri, jika tidak anda boleh mencari kunci di sebelah kanan (tengah+1, kanan)

• Jika kunci tidak dijumpai di tengah, dan bahagian kiri tidak diisih, maka kita akan menyusun bahagian kanan, dan kemudian kita boleh melihat sama ada kunci itu wujud di bahagian kanan, atau kita akan mencari tatasusunan di bahagian kanan Bahagian kiri

• Jika tidak kami akan kembali yang tidak dapat ditemui.

Mari kita lihat beberapa senario input dan output di bawah -

Bayangkan terdapat array yang terdiri daripada elemennya. Contohnya, 2, 5, 7, 9, 11, selepas putaran, menjadi 5, 9, 11, 2, 7. Katakan kunci tatasusunan ialah 2.

Input: arr[] = {5, 9, 11, 2, 7}, Key=2
Output: Element "2" found at 3rd index

Mari kita anggap satu lagi senario di mana kunci tidak berada dalam tatasusunan yang ditentukan.

Input: arr[] = {10, 23, 45, 77, 84}, Key=90
Output: Element "90" not found.

Algoritma

Langkah berikut adalah cara untuk mencapainya.

• Cari elemen tengah tatasusunan.

• Pahasi tatasusunan kepada dua bahagian. (tengah = kiri + kanan) / 2

• Periksa sama ada kunci ialah elemen perantaraan.

• Lain jika , semak elemen di sebelah kiri tatasusunan dan ia diisih

• lain jika, tandakan elemen yang betul (pertengahan+1, kanan)

• Jika tidak, susun bahagian kiri dan semak

• Jika tidak, kembalikan elemen yang tidak ditemui.

Contoh

Sebagai contoh, katakan kita mempunyai tatasusunan "2,3,4,5,6,7,8", dan tatasusunan yang diputar ialah "5,6,7,8,2,3,4". Kunci tatasusunan ini ialah 2.

Pelaksanaan C++ bagi operasi ini adalah seperti berikut -

#include <iostream>
#include <vector>
using namespace std;
bool solve(vector<int> arr, int left, int right, int key) {
   if (left > right) {
      return false;
   }
   int mid = (left + right)/2;
   if (arr[mid] == key) {
      return true;
   }
   if (arr[left] <= arr[mid]) {
      if (key >= arr[left] && key <= arr[mid]) {
         return solve(arr, left, mid-1, key);
      }
      return solve(arr, mid+1, right, key);
   }
   if (key >= arr[mid] && key <= arr[right])
      return solve(arr, mid+1, right, key);
   return solve(arr, left, mid-1, key);
}
int main() {
   vector<int> arr = {5, 6, 7, 8, 2, 3, 4};
   int key = 2;
   if(solve(arr, 0, arr.size()-1, key)) cout << key << " is present";
      else cout << key << " is not present";
   return 0;
}

Output

2 is present

KESIMPULAN

Cara lain untuk menyelesaikan masalah ini ialah mencari titik pangsi atau indeks putaran tatasusunan dan kemudian lakukan carian binari pada tepi. Kaedah kami hanya memerlukan 1 carian binari untuk menyelesaikan masalah. Setiap kali kita melihat mencari dan menyusun tatasusunan, kita harus menganggap carian binari sebagai salah satu kaedah carian.

Atas ialah kandungan terperinci Program C++ untuk mencari elemen dalam tatasusunan yang disusun dan diputar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!