Ye Olde Binary Search
culliton at clark.net
Fri Mar 31 22:57:55 CEST 2000
In article <an6F4.2066$HG1.59245 at nnrp1.uunet.ca>,
Warren Postma <embed at geocities.com> wrote:
>Is there a builtin somewhere in Python to do a binary search on a list?
Have you read the library reference manual? It describes all builtin
and standard library functions. For example the bisect module which
does ordered inserts. RTFM. (around here 'F' is for "friendly")
>2. Is there faster way to check if a list is sorted than just always calling
Probably not, unless you write a module to do it.
>3. Has anyone written a faster/better one of these in native C?
As above, check the library reference manual. Also check the web
sites, for example, http://www.vex.net/parnassus/ for prior art.
>4. Has anyone ever considered an "inorder_insert" and a "search" method be
>added to the built-in Python list type, making it a auto-sorted-array with
>fast searching, if we so desired? If there is a good solution to #2, would
>it be possible for search to note quickly that a list is in sorted order,
>and therefore use the faster binary search, otherwise it would use a slower
>iterative search (The Bad Old Way).
A bsearch method for sequences might be a good 1.6 wish list item for
the bug list. If it's already there add your vote.
More information about the Python-list