在未排序的數組中進行前後搜索

未排序陣列 - 陣列是由相同類型的元素集合所組成的資料結構。未排序數組是這樣一種結構，其中元素的順序是隨機的，即在插入時，無論先前元素的順序如何，該元素都會添加到最後一個元素，並且在這樣的數組中進行搜索不會受到任何搜尋演算法的幫助，因為缺乏元素定位的模式。

搜尋 - 在陣列中搜尋意味著在陣列中尋找特定元素，該元素可以傳回所需元素的位置，也可以傳回一個bool 語句，指定該元素是否存在於陣列中或不是。

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

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

問題陳述

給定一個搜尋元素 x，找出 x 是否存在於下列情況 -

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

• 具有不同大小元素的數組，字串數組。

範例 1

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

Output: TRUE

解釋 - 在給定陣列中，4 出現在第二個索引處。

範例 2

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

Output: False

解釋 - 在給定的陣列中，「high」不存在。

解決方案

如上所述，前向搜尋從第一個元素開始，後向搜尋從最後一個元素開始。將這兩種方法結合在一起，由於同時檢查數組的前半部分和後半部分，因此在數組中搜尋元素的時間可以減少兩倍。

要尋找某個元素是否出現在陣列中，請將first 和last 定義為陣列的第一個和最後一個元素。如果第一個或最後一個元素中的任何一個是所需元素，則傳回 true，否則第一個元素遞增 1，最後一個元素遞減 1，然後繼續，直到找到該元素。如果遍歷完成時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 實作

在下面的程式中，我們採用整數陣列的第一種情況。取得第一個和後一個變量，同時檢查第一個和最後一個元素以找到所需的元素。如果找到該元素，則傳回 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)

範例

在下面的程式中，我們採用字串陣列的第二種情況。取得第一個和後一個變量，同時檢查第一個和最後一個元素以找到所需的元素。如果找到該元素，則傳回 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)。

以上是在未排序的數組中進行前後搜索的詳細內容。更多資訊請關注PHP中文網其他相關文章！