26hmkk - 1 year ago 71

Java 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 Source

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