7 ms·
Part of it must be that binary search only works on a sorted array, and most arrays won't be sorted. Followup question: are there other common array operations
by pmahoney 14y ago
Part of it must be that binary search only works on a sorted array, and most arrays won't be sorted.
Followup question: are there other common array operations that only work on arrays in a particular state? Are any of these in or out of various standard libraries?
A long time ago... I implemented a wrapper around the Gnu Scientific Library matrix operations. I recall trying to be clever by mixing in some extra methods only after getting the LU decomposition (these extra methods required the matrix to be in a specific state). A little too dynamic for my current tastes. It's not a terrible idea perhaps, but this sort of thing tends to kill performance.
- kylebgorman 14y agoA good example of an array operation only appropriate for specific states is Python's treatment of heaps: http://docs.python.org/2/library/heapq.html http://docs.python.org/2/library/heapq.html You need to heapify(your_array) in place before, e.g., calling nsmallest(your_array). Not saying that it's good style, but...
- fusiongyro 14y agoIt's interesting that in Smalltalk there is a SortedCollection class which guarantees this state, and in general you can sort by calling #asSortedCollection on your collection. Presumably the search methods on that class are O(log N) rather than O(N).