26hmkk 26hmkk - 6 months ago 17
Java Question

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

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

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).

Comments