What Is Quicker: Using Quicksort then Binary Search OR Just Linear Search?

Question

If I had an array of integers with 1000 elements, what would be the fastest way to find a specific element's index? Would it be best to first QuickSort it and then use BinarySearch or just to use plain old LinearSearch?

Also, would the fastest method be different if I had 100 000 elements or even just 100 elements?

Thanks!

Answer 1

Linear search would be better. The worst case of O(N) for linear search is less than quicksort alone (average O(nlog n) but worst case O(N^2)) and then you would need to add the binarysearch (O(log N)). Sorting and using binary search would be better if you need to search many times (if you can amortize the sorting cost, then binary search is more efficient than linear search).

Answer 2

As the other answers say, linear search is better if you only want to find one member of the list. But if you want to find many members of the same list, then you'd be better off sorting it one time, and then doing many binary searches.