Cari ke hadapan dan ke belakang dalam tatasusunan yang tidak diisih

Unsorted Array - Tatasusunan ialah struktur data yang terdiri daripada himpunan elemen daripada jenis yang sama. Tatasusunan yang tidak diisih ialah struktur di mana susunan unsur-unsur adalah rawak iaitu pada sisipan, elemen itu ditambahkan pada elemen terakhir tanpa mengira susunan unsur-unsur sebelumnya dan carian dalam tatasusunan sedemikian tidak mengalami sebarang bantuan algoritma Carian kerana kekurangan corak kedudukan elemen.

Cari - Mencari dalam tatasusunan bermakna mencari elemen tertentu dalam tatasusunan, yang boleh mengembalikan kedudukan elemen yang diingini atau pernyataan bool yang menyatakan sama ada elemen itu hadir dalam tatasusunan atau tidak.

• Cari ke hadapan - Mencari ke hadapan dalam tatasusunan bermakna melakukan pencarian linear bagi tatasusunan bermula dari indeks ke-0 (iaitu elemen pertama).

• Carian Terbalik - Mencari tatasusunan secara terbalik bermakna melakukan pencarian linear bagi tatasusunan bermula dari indeks (n-1) ke (iaitu elemen terakhir).

Pernyataan Masalah

Diberi unsur carian x, cari jika x wujud dalam kes berikut -

• Tatasusunan dengan elemen saiz yang sama, tatasusunan integer.

• Tatasusunan dengan elemen saiz yang berbeza, tatasusunan rentetan.

Contoh 1

Input: x = 4, [6, 1, 4, 10, 2]

Output: TRUE

Penjelasan - Dalam tatasusunan yang diberikan, 4 muncul pada indeks kedua.

Contoh 2

Input: x = “high”, [“goat”, “ice”, “hgh”]

Output: False

Penjelasan - Dalam tatasusunan yang diberikan, "tinggi" tidak wujud.

Penyelesaian

Seperti yang dinyatakan di atas, carian ke hadapan bermula dari elemen pertama dan carian ke belakang bermula dari elemen terakhir. Menggabungkan kedua-dua kaedah ini, masa mencari elemen dalam tatasusunan boleh dikurangkan sebanyak dua kali sejak separuh pertama dan kedua tatasusunan diperiksa serentak.

Untuk mengetahui sama ada elemen muncul dalam tatasusunan, takrifkan pertama dan terakhir sebagai elemen pertama dan terakhir tatasusunan. Mengembalikan benar jika sama ada elemen pertama atau terakhir ialah elemen yang diperlukan, jika tidak menambah elemen pertama sebanyak 1, mengurangkan elemen terakhir sebanyak 1 dan berterusan sehingga elemen ditemui. Jika pertama dan terakhir adalah sama apabila traversal selesai, maka false dikembalikan jika elemen tidak dijumpai.

pseudokod

procedure frontBack (arr[], x)
   first = 0
   last = n - 1
   while first <= last
      If arr[first] == x or arr[last] == x
         ans = true
       end if
      front = front + 1
      last = last - 1
   ans = false
end procedure

Contoh: Pelaksanaan C++

Dalam atur cara berikut, kami mengambil kes pertama tatasusunan integer. Dapatkan pembolehubah pertama dan seterusnya sambil menyemak elemen pertama dan terakhir untuk mencari elemen yang diperlukan. Jika elemen ditemui, kembalikan benar, jika tidak pergi ke elemen seterusnya dan semak semula.

#include <bits/stdc++.h>
using namespace std;
// Function to front back search an element in the array
bool frontBack(int arr[], int x){
   int first = 0, last = 9;
   
   // loop execute till the element is found or traversal completes
   while (first <= last){
      if (arr[first] == x || arr[last] == x){
         return true;
      }
      first++;  // Incrementing first
      last--;  // Decrementing last
   }
   return false;
}
int main(){
   int arr[10] = {21, 43, 10, 19, 3, 56, 91, 20, 5, 79};
   int x = 55;
   cout << "In the array : ";
   for (int i = 0; i < 10; i++){
      cout << arr[i] << " ";
   }
   cout << "\nElement " << x;
   if (frontBack(arr, x)){
      cout << " is present.";
   }
   else{
      cout << " is not present.";
   }
   return 0;
}

Output

In the array : 21 43 10 19 3 56 91 20 5 79 
Element 55 is not present.

Kerumitan masa - O(n/2) sejak mencari dari kedua-dua belah memotong masa kepada separuh.

Kerumitan ruang - O(1)

Contoh

Dalam program di bawah, kami mengambil kes kedua tatasusunan rentetan. Dapatkan pembolehubah pertama dan seterusnya sambil menyemak elemen pertama dan terakhir untuk mencari elemen yang diperlukan. Jika elemen ditemui, kembalikan benar, jika tidak pergi ke elemen seterusnya dan semak semula.

#include <bits/stdc++.h>
using namespace std;
// Function to front back search an element in the array
bool frontBack(string arr[], string x){
   int first = 0, last = 9;
   
   // loop execute till the element is found or traversal completes
   while (first <= last)    {
      if (arr[first] == x || arr[last] == x)        {
         return true;
      }
      first++; // Incrementing first
      last--; // Decrementing last
   }
   return false;
}
int main(){
   string arr[4] = {"hi", "high", "goat", "goa"};
   string x = "goat";
   cout << "In the array : ";
   for (int i = 0; i < 4; i++) {
      cout << arr[i] << ", ";
   }
   cout << "\nElement " << x;
   if (frontBack(arr, x)) {
      cout << " is present.";
   }
   else {
      cout << " is not present.";
   }
   return 0;
}

Output

In the array : hi, high, goat, goa, 
Element goat is present.

Kerumitan masa - O(n/2) sejak mencari dari kedua-dua belah memotong masa kepada separuh.

Kerumitan ruang - O(1)

Kesimpulan

Untuk meringkaskan, carian ke hadapan dan ke belakang tatasusunan adalah serupa dengan carian linear biasa, kecuali ia menyemak dua elemen pada masa yang sama, sekali gus mengurangkan penggunaan masa kepada separuh. Ini mengubah kerumitan masa terburuk untuk mencari dalam tatasusunan yang tidak diisih daripada O(n) kepada O(n/2).

Atas ialah kandungan terperinci Cari ke hadapan dan ke belakang dalam tatasusunan yang tidak diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!