无序数组中的前后搜索

---

无序数组 − 数组是一种数据结构，由相同类型的元素集合组成。无序数组是一种这样的结构，其中元素的顺序是随机的，即在插入时，元素被添加到最后，而不管先前元素的顺序如何，并且由于缺乏元素位置模式，任何搜索算法都不能帮助在这种数组中进行搜索。

搜索 − 在数组中搜索意味着查找数组中的特定元素，这可以是返回所需元素的位置，也可以是返回一个布尔语句，说明该元素是否存在于数组中。

• 前向搜索 − 前向搜索数组意味着从第 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)。