未排序陣列 - 陣列是由相同類型的元素集合所組成的資料結構。未排序數組是這樣一種結構,其中元素的順序是隨機的,即在插入時,無論先前元素的順序如何,該元素都會添加到最後一個元素,並且在這樣的數組中進行搜索不會受到任何搜尋演算法的幫助,因為缺乏元素定位的模式。
搜尋 - 在陣列中搜尋意味著在陣列中尋找特定元素,該元素可以傳回所需元素的位置,也可以傳回一個bool 語句,指定該元素是否存在於陣列中或不是。
前搜尋 - 前搜尋陣列意味著從第 0 個索引(即第一個元素)開始對陣列進行線性搜尋遍歷。
反向搜尋 - 反向搜尋陣列意味著從第(n-1)個索引(即最後一個元素)開始對陣列進行線性搜尋遍歷。
給定一個搜尋元素 x,找出 x 是否存在於下列情況 -
具有相同大小元素的陣列,整數陣列。
具有不同大小元素的數組,字串數組。
Input: x = 4, [6, 1, 4, 10, 2]
Output: TRUE
解釋 - 在給定陣列中,4 出現在第二個索引處。
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
在下面的程式中,我們採用整數陣列的第一種情況。取得第一個和後一個變量,同時檢查第一個和最後一個元素以找到所需的元素。如果找到該元素,則傳回 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中文網其他相關文章!