無序陣列中的前後搜尋

---

無序陣列 − 陣列是一種資料結構，由相同型別的元素集合組成。無序陣列是一種這樣的結構，其中元素的順序是隨機的，即在插入時，元素被新增到最後，而不管先前元素的順序如何，並且由於缺乏元素位置模式，任何搜尋演算法都不能幫助在這種陣列中進行搜尋。

搜尋 − 在陣列中搜索意味著查詢陣列中的特定元素，這可以是返回所需元素的位置，也可以是返回一個布林語句，說明該元素是否存在於陣列中。

• 前向搜尋 − 前向搜尋陣列意味著從第 0 個索引（即第一個元素）開始對陣列進行線性搜尋遍歷。

• 後向搜尋 − 後向搜尋陣列意味著從第 (n-1) 個索引（即最後一個元素）開始對陣列進行線性搜尋遍歷。

問題陳述

給定一個搜尋元素 x，查詢 x 是否存在於以下情況下：

• 一個具有相同大小元素的陣列，一個整數陣列。

• 一個具有不同大小元素的陣列，一個字串陣列。

示例 1

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

Output: TRUE

解釋 − 在給定的陣列中，4 位於第 2 個索引。

示例 2

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

Output: False

解釋 − 在給定的陣列中，“high”不存在。

解決方案

如上所述，前向搜尋從第一個元素開始，後向搜尋從最後一個元素開始。將這兩種方法結合起來，可以將搜尋陣列中元素的時間減少一半，因為同時進行陣列前半部分和後半部分的檢查。

為了查詢元素是否出現在陣列中，將 first 和 last 分別定義為陣列的第一個和最後一個元素。如果第一個或最後一個元素是所需元素，則返回 true；否則，將 first 加一，將 last 減一，並繼續直到找到該元素。如果在完全遍歷後 first 和 last 都相等，則找不到該元素，然後返回 false。

虛擬碼

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

示例：C++ 實現

在下面的程式中，我們採用整數陣列的第一種情況。使用 first 和 back 變數，同時檢查第一個和最後一個元素以查詢所需元素。如果找到元素，則返回 true；否則，繼續檢查下一個元素。

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

輸出

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

時間複雜度 − O(n/2)，因為從兩側搜尋將時間減少了一半。

空間複雜度 − O(1)

示例

在下面的程式中，我們採用字串陣列的第二種情況。使用 first 和 back 變數，同時檢查第一個和最後一個元素以查詢所需元素。如果找到元素，則返回 true；否則，繼續檢查下一個元素。

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

輸出

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

時間複雜度 − O(n/2)，因為從兩側搜尋將時間減少了一半。

空間複雜度 − O(1)

結論

總之，陣列的前向和後向搜尋類似於普通的線性搜尋，不同之處在於它將時間消耗減少了一半，因為它同時檢查兩個元素。因此，將無序陣列中搜索的最壞情況時間複雜度從 O(n) 轉換為 O(n/2)。