Ye Olde Binary Search

[Tom Culliton]

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

http://www.python.org/doc/current/lib/lib.html
http://www.python.org/doc/current/lib/module-bisect.html

>2. Is there faster way to check if a list is sorted than just always calling
>list.sort()?

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.