4 ms·

I did a quick [1] google around some of the most popular programming languages to see if their stdlibs had binary search: Python: No Perl: No PHP: No Lua: No J

I did a quick [1] google around some of the most popular programming languages to see if their stdlibs had binary search: Python: No Perl: No PHP: No Lua: No Java: Yes .NET: Yes Objective-C: Yes Of course your point then becomes "Why haven't Ruby, Python, Perl, PHP and Lua added binary search". [1] So it may be wrong. Please correct me if I am.

Hinrik 14y ago
For Lua at least, it's not surprising. Its standard library is deliberately extremely minimal. There are no functions to search tables (Lua's datastructure for collections), not even linearly.
rraval 14y ago
Python: http://docs.python.org/2/library/bisect.html http://docs.python.org/2/library/bisect.html
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 ago
  A 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 ago
  It'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).
kylebgorman 14y ago
Python has the stdlib module "bisect" which does binary search.

Hinrik 14y ago

For Lua at least, it's not surprising. Its standard library is deliberately extremely minimal. There are no functions to search tables (Lua's datastructure for collections), not even linearly.

rraval 14y ago

Python: http://docs.python.org/2/library/bisect.html http://docs.python.org/2/library/bisect.html

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 ago
A 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 ago
It'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).

kylebgorman 14y ago

Python has the stdlib module "bisect" which does binary search.