[Tutor] Binary search question

Steven D'Aprano steve at pearwood.info
Sat Apr 24 04:11:07 CEST 2010

On Sat, 24 Apr 2010 10:37:15 am Steven D'Aprano wrote:
> For the record, here's some timing benchmarks to see how badly it
> turned out:
> 0.0346097946167
> 0.461233854294
> 3.04955101013
> 5.70547604561
> For comparison, here's the timing on a plain binary search:

Oops, I hit send too soon and forgot the timing. Here it is:


So about 10 times faster than a linear search on 10,000 items. Not to be 
sneezed at, but unless the time taken by your program is dominated by 
the searches, I probably wouldn't bother with the extra complexity.

Steven D'Aprano

More information about the Tutor mailing list