3 ms·
I also think he should have covered the time it would take to sort an array. A linear search wouldn't need to be sorted, but a binary search would. He made his
by alphonse23 12y ago
I also think he should have covered the time it would take to sort an array. A linear search wouldn't need to be sorted, but a binary search would. He made his cut off at around 64 elements, but if you'd include the time needed by binary search to sort the array, the cut off limit would be a higher than that -- but would also introduce a lot of other complexities to consider in a production system.
- lgeek 12y agoI really doubt there's any data size for which sort + binary search is going to be faster than linear search. The former has higher complexity (so it's going to be slower for large inputs) and more expensive operations (so it will be slower for small inputs). You can also think about it as a sort of reductio ad absurdum: Assume that the array is actually already sorted and you use a sorting algorithm with O(n) complexity for already sorted data. In this ideal case you'd need to do n (for sorting) + log n (binary search) predictable operations. For linear search you'd only need to n operations of the same type. In practice you'd need to do n log n operations for sorting, I don't think you can avoid unpredictable branches, and instead of just loading elements sometimes you'll move them around.
- exDM69 12y agoI think the assumption is that you sort once and search several times (enough to amortize the cost of the sort). The linear search algorithm also had an early exit, so the array has to be sorted for that too. That makes this a fair comparison, but I agree that seeing a linear unsorted search would have been interesting too.