arrays - 查找元素是否存在于未排序数组中的最快方法？

Question

搜索未排序数组以进行元素线性搜索的最快算法是什么？我的意思是我猜合并排序+二进制搜索的组合会更慢。还有其他选择吗？（就不涉及多线程的算法而言）？

Answer 1

是的，如果数组是未排序的并且这就是你所知道的关于它的结构，那么搜索一个元素的最快方法是考虑每一个需要线性时间O(n)的元素。

如果您要大量搜索数组，那么您可能需要考虑进行初始排序，然后将元素插入到正确的排序索引中（使用二进制搜索）。这意味着您的初始排序为O(n log n)但每次插入和搜索都需要O(log n)。这都是关于权衡以及这是否比O(1)插入和O(n)搜索更好。

您说没有多线程，但这是提高性能的一种简单方法，让多个线程查看列表中的不同块。

Answer 2

我创建了一种在未排序数组中搜索元素的方法。

#include <iostream> 
#include <vector> // for 2D vector 
#include<bits/stdc++.h>
using namespace std; 

int main() 
{ 
    vector<vector<int>> vect{ {0},{0},{0},{0},{0},{0},{0},{0},{0},{0} }; 
    int count[10];
    int min = INT_MAX; 
    int max = INT_MIN;   
    for (int i = 0; i < 10; i++)
    {
        count[i] = 0;
    }

    for (int i = 0; i < 7; i++)
    {
        //input 7 integers
        int ip,
            rem;
        cin >> ip;
        rem = ip % 10;
        if (ip > max)
            max = ip;
        if (min > ip)
            min = ip;
        if (vect[rem][0] == 0 && count[rem] == 0)
        {
            vect[rem][0] = ip;
            count[rem]++;
        }
        else
        {
            vect[rem].push_back(ip);
            count[rem]++;
        }
    }

    int find;
int flag = 0;
    cin >> find;
    int rem = find % 10;
    if (find>max || find<min || count[rem] == 0)
        cout<<"not present in the array";
    else
    {
        for (int i = 0; i < vect[rem].size(); i++)
        {
            if (vect[rem][i] == find)
            {
                cout << "found";flag = 1;
                break;
            }
        }
      if(flag == 0)
        cout<<"not present in the array";
    }

    return 0; 
}

我看到这可以更快。基本上，一旦收到元素，我就会将元素存储在 2D 矢量中。

我将剩余的数字（数字 % 10）作为向量的索引并推送这些元素。现在要搜索元素，我只遍历向量的特定索引中存在的元素。
这样，比较的次数就少了。