Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fastest way to search for an element in unsorted array

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.

like image 726
Ajai Avatar asked Oct 05 '11 04:10

Ajai


People also ask

Which is the fastest search algorithm for unsorted array?

Which is the fastest search algorithm for unsorted array? If the array is not sorted then you have to search for the element by iteration ,linear search . There is no better way than O(n).

Which search is best for unsorted array?

Binary Search. Sequential search is the best that we can do when trying to find a value in an unsorted array.

What is the best way to search an unsorted list?

Linear search can be used to search for the smallest or largest value in an unsorted list rather than searching for a match. It can do so by keeping track of the largest (or smallest) value and updating as necessary as the algorithm iterates through the dataset.


2 Answers

Make it parallel. Divide the array in chunks and search in parallel. The complexity will be O(n) but running time will be much less. Actually it will be proportional to no. of processors you have.

You can use Parallel Patterns Library in C++

like image 77
Muhammad Hasan Khan Avatar answered Oct 09 '22 02:10

Muhammad Hasan Khan


You're right, the fastest way is to simply iterate through the array and look for it. Without further information, there is nothing better you can do.

Unless you have a quantum computer, that is.

like image 30
Keith Randall Avatar answered Oct 09 '22 03:10

Keith Randall