Самый быстрый способ поиска элемента в несортированном массиве

Я просто столкнулся с этим вопросом сегодня и пытался найти решение, которое лучше, чем O (N), но не могло придумать его.

Искал через SO, но не смог найти этот вопрос.

Есть ли какое-либо решение лучше, чем O (n), или это проблема, которая не может быть решена лучше этого?

Моя первоначальная мысль была Binary Search, но снова для этого вам нужно отсортировать ее, что сновa > n. Я также думал о применении quicksort только для половины массива, к которому может принадлежать элемент поиска, но мы сначала делаем n сравнений и отбрасываем вторую половину только позже. Правильно ли это, или я смотрю на решение в неправильном направлении?

Я пытался найти решение в С++ и не индексировал JavaScript IndexOf() или С# Array.find() или LINQ.

Ответ 1

Сделайте его параллельным. Разделите массив на куски и выполните поиск параллельно. Сложность будет равна O (n), но время работы будет намного меньше. На самом деле это будет пропорционально no. процессоров, которые у вас есть.

Вы можете использовать Библиотека параллельных шаблонов на С++

Ответ 2

Вы правы, самый быстрый способ - просто перебирать массив и искать его. Без дополнительной информации ничего лучше не получится.

Если у вас нет квантового компьютера, то есть.

Ответ 3

Если вы ищете один элемент один раз, просто перейдите через него. Нет возможного способа получить его быстрее.

Если вы много раз искали, было бы целесообразно его индексировать (или отсортировать, если хотите) и быстро выполнить следующие поисковые запросы (log (n)).

Ответ 4

Если он не отсортирован, вам необходимо проверить каждый элемент.

Ответ 5

Вы можете искать элемент с O (1), используя этот подход.

Просто создайте КАРТУ. Когда вы просто вставляете значение для этого ключа, присвойте ему значение "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*

Выход: НАЙДЕН

Ответ 6

Тем не менее, есть другая логика...

(Четные числа хранятся в четном адресе)

Сначала проверьте, является ли элемент поиска нечетным или четным
Если элементом поиска является "четный", то выполнять поиск только по четному адресу (Создать шаг приращения, чтобы пропустить нечетный адрес)
Половина элемента может быть пропущена из поиска по этой логике

Например:

Если 100 элементов хранятся в неупорядоченном виде, а поисковый элемент - 98.... поскольку номер поиска четный... вы можете пропустить все нечетные адреса (пропускается 50 элементов). Теперь поиск выполняется только для остальных 50 четных адрес....

Вы можете разделить элемент и выполнить параллельный поиск или использовать "поворотный ключ", чтобы отсортировать остальные 50 элементов, или любой другой метод поиска.

Ответ 7

Какова будет эффективность алгоритма, который использует подход разбиения, применяемый во время быстрой сортировки, следующим образом?

Случайно выберите какое-либо значение (назовем его v) в списке.
Разбейте весь список на 2 части. Левая часть содержит все элементы, которые меньше, чем v. Правая часть содержит все элементы, которые больше, чем v.
Повторяйте шаги 2, 3, пока не определите, существует элемент или не существует.

Я не уверен в сложности вышеприведенного алгоритма, но похоже, что он определенно будет меньше сложности алгоритма быстрой сортировки: (n log n).

Ответ 8

Возможно заставить вашу программу работать быстрее чем O(n).

Вы начинаете с сортировки массива с использованием алгоритма сортировки слиянием, а затем используете бинарный поиск, чтобы найти элемент. Оба алгоритма имеют время работы O(log_2(n)). Сложив эти две сложности вместе, вы получите 2*log_2(n), что равно O(log_2(n)) со свидетелем C = 2.