algorithm - Fastest way to find if element exists in an unsorted array?

Question

Is the fastest algorithm for searching an unsorted array for an element linear search? I mean I guess a combination of merge sort + binary search would be slower. Are there any other options? (in terms of algorithms not involving multithreading)?

Answer 1

Yes, if the array is unsorted and that's all you know about its structure then the fastest way to search for an element is to consider every one which takes linear time O(n).

If you are going to be searching the array a lot then you may want to consider an initial sort and then insert elements into their correct sorted index (using binary search). This means that you have your initial sort as O(n log n) but each insert and search takes O(log n). It's all about tradeoffs and whether that is better than O(1) insert and O(n) search.

You said no multithreading but that is an easy way to boost performance, have multiple threads look at different chunks in the list.