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

Question

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

Поиск в SO, но не смог найти этот вопрос.

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

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

Я пытался найти решение в c ++, а не в IndexOf () или C # Array.find () или LINQ в javascript.

Answer 1

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

Вы можете использовать Parallel Patterns Library в C ++

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

1. Случайно выберите какое-либо значение (назовем его v) в списке.

2. Разделите весь список на 2 части. Левая часть содержит все элементы, которые меньше v. Правая часть содержит все элементы, которые больше v.

3. Повторяйте шаги 2, 3, пока не определите, существует элемент или не существует.

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

Answer 6

Еще есть другая логика ...

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

• Сначала проверьте, найден ли поискэлемент нечетный или четный

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

• Половина элемента может быть пропущена из поиска по этой логике

Например:

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

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

Answer 7

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

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

Answer 8

Вы можете искать элемент с 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*

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