Fastest way to search for an element in unsorted a

Question

I just bumped on to this question today and was trying for a solution that is better than O(N) but could not come up with one.

Searched through SO but couldn't find this question.

Is there any solution better than O(n) or is it a problem that cannot be solved better than that?

My initial thought was Binary Search but again for that you need to sort it which is again >n. I also thought of applying quicksort for just the half of the array to which the search element might belong but again we are making n comparisons initially and discarding the other half only later. Am I getting this right or am I looking at the solution in a wrong direction?

I was trying for a solution in c++ and no javascript's IndexOf() or C# Array.find() or LINQ's.

Answer 1

What will be the efficiency of algorithm that makes use of partition approach applied during quick-sort as follows?

1. Randomly select some value (let us call it v) in the list.

2. Partition the entire list into 2 parts. Left part contains all elements that are less than v. Right part contains all elements that are greater than v.

3. Repeat the steps 2, 3 until you determine whether the element exists or does not exist.

I am not sure about the complexity of above algorithm, but looks like it will be definitely less than the complexity of quick-sort algorithm: (n log n).

Answer 2

You can search an element with O(1) using this approach.

Just create a MAP . When you insert a value just then for that key assign value to '1', and to search it again just check if that array is present or not .

Below is the code:-

#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*

Output :FOUND

Answer 3

It is possible to make your program run faster than O(n).

You start off by sorting the array using the merge sort algorithm, then you use binary search to find the element. Both algoro have a running time of O(log_2(n)). Adding these two complexities together, you get 2*log_2(n), which is O(log_2(n)) with the witness C = 2.

Answer 4

Yet,there is another logic...

(Even numbers are stored in even address)

• First check whether the search element is odd or even

• If the search element is"even",then perform search only for even adress(Create loop increment to skip odd address)

• Half the element can be skipped from searching by this logic

For example:

• If there are 100 element stored in unordered way and search element is 98.... since the search number is even...u can skip all odd address(so 50 elements are skipped) Now the search is done only for rest 50 even address....

You can divide the element and search in parallel or Use "pivot key" to sort to rest 50 elements or any other search method

Answer 5

If you're searching for one element once, just iterate through it. No possible way to get it faster.

If you're searching multiple times, it would be worth it to index it (or sort it, if you will) and make the following searches fast (log(n)).

Answer 6

If it's not sorted, you have to inspect each element.