首頁  >  文章  >  後端開發  >  在未排序的數組中進行前後搜索

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

WBOY
WBOY轉載
2023-09-06 23:45:05753瀏覽

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

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

搜尋 - 在陣列中搜尋意味著在陣列中尋找特定元素,該元素可以傳回所需元素的位置,也可以傳回一個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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除

相關文章

看更多