今天我偶然看到了这个问题，尝试找到一个比O(N)更好的解决方案，但却没有想出来。
在SO上搜索了一下，但没有找到这个问题。
有没有比O(n)更好的解决方案，或者说这是一个不能比O(n)更好地解决的问题？
我的第一个想法是二分查找，但是为了使用它，需要对其进行排序，这又是>n的复杂度。我还考虑过只对可能包含搜索元素的数组的一半应用快速排序，但是我们最初要进行n次比较，之后才将另一半丢弃。我是正确理解问题，还是我的解决方向有误？
我正在尝试在c++中找到一个解决方案，而不是使用javascript的IndexOf()、C#的Array.find()或LINQ。
并行化处理。将数组分成多个块，并进行并行搜索。虽然复杂度仍为O(n)，但运行时间会大大缩短。实际上，它与处理器数量成正比。
在C++中，您可以使用并行模式库。
您说得对，最快的方法是简单地遍历数组并查找它。没有更多信息的情况下，您无法做得更好。
除非您拥有一个量子计算机。
n 相当数量的处理器（即可数无限多的处理器），否则它不会改变渐近时间。 - user684934O 到底意味着什么。-_- - ELLIOTTCABLEfor(int i=0;i<s;i++){ // s = array size
if(arr[i] == n) // n = element to be searched
return i;
}
但我实验的是在单个迭代中检查多个元素，例如每次5个元素。因此，在这种情况下，for循环将如下所示：
// s = array size
// n = element to be searched
for(int i=0;i<s;i+=5){ // notice the increment in i here...
if(arr[i] == n)
return i;
/* check the next four indexes as well as if arr[i] is the last element of the array */
else if( arr[i+1] == n && i+1 < s)
return i+1;
else if(arr[i+2] == n && i+2 < s)
return i+2;
else if(arr[i+3] == n && i+3 < s)
return i+3;
else if(arr[i+4] == n && i+4 < s)
return i+4;
}
理论上，时间复杂度应该变为 O(n/5)…
但是，当我使用大小为1000000的数组进行测试，其中元素1到1000000随机排列，并计算两个循环对于相同数组大小的不同测试用例所需的时间……结果如下：
每次迭代一个元素
每次迭代五个元素
因此，我发现这确实对时间复杂度产生了显着影响！
使用这种方法可以在O(1)时间内搜索元素。
只需创建一个MAP。当您插入一个值时，为该键分配值'1'，再次搜索它时，只需检查该数组是否存在即可。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
map<int,int> map;
for(int i=0;i<n;i++){
int k;
cin>>k;
map[k]=1;
}
int num;
cin>>num;
if(map[num]){
cout<<"FOUND"<<endl;
}else{
cout<<"NOT FOUND"<<endl;
}
return 0;
}
Input:
5 // *no. of elements*
6 4 7 3 2 //*elements*
3 // *number to find*
输出：找到了
只需遍历一次数组，检查有多少个数字小于该特定数字。
在寻找比线性搜索更快的方法时，我刚好发现了“前后”线性搜索方法（https://medium.com/@insomniocode/search-algorithm-front-and-back-unsorted-86d7a4bfc258），我在几个实例上测试过，结果确实更快，但并没有显著提高。在我看来值得一试！
这个问题可以通过使用一些技巧来解决。在未排序的数组中，如果我们遍历它，最坏情况下（当元素位于最后一个索引时）的复杂度将为O(N)，其中N是数组的大小。所以，这里有一个技巧。首先检查最后一个索引，这样如果元素位于最后一个索引（最坏情况），我们的代码将在O(1)中执行。然后再执行遍历和查找元素的代码。因此，现在最坏情况下的复杂度将为O(N-1)。
int findElement(int N, int arr[], int element){
if(arr[N]==element){
return i;
}
for(int i=0; i<N-1; i++){
if(arr[i]==element)
return i;
}
return -1;
}
O(n)更好。 - Mysticial