未排序数组 – 数组是由相同类型的元素集合组成的数据结构。未排序数组是这样一种结构，其中元素的顺序是随机的，即在插入时，无论先前元素的顺序如何，该元素都会添加到最后一个元素，并且在这样的数组中进行搜索不会受到任何搜索算法的帮助，因为缺乏元素定位的模式。
搜索 – 在数组中搜索意味着在数组中查找特定元素，该元素可以返回所需元素的位置，也可以返回一个 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 = falseend procedure
示例：C++ 实现
在下面的程序中，我们采用整数数组的第一种情况。获取第一个和后一个变量，同时检查第一个和最后一个元素以找到所需的元素。如果找到该元素，则返回 true，否则转到下一个元素并再次检查。
#include using namespace std;// Function to front back search an element in the arraybool 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 using namespace std;// Function to front back search an element in the arraybool 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)。
以上就是在未排序的数组中进行前后搜索的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444534.html
微信扫一扫 
支付宝扫一扫 
