liveBook · Manning

Bisection algorithm

As explained in Fast Python: High performance techniques for large datasets

A bisection algorithm repeatedly divides an ordered search range to locate a target or insertion position.

A bisection algorithm repeatedly divides an ordered search range to locate a target or insertion position. For interval searches, it makes an ordered list a stronger choice than repeatedly looking up every element in a set or dictionary. section 2.3.3

Use the technique when:

  • The values are ordered and the search concerns a range rather than one exact key. section 2.3.3
  • A linear membership scan through a large list could become a production bottleneck. section 2.3.3
  • You need to weigh the simplicity of lists against specialized set or dictionary lookups. section 2.3.3

How Fast Python: High performance techniques for large datasets covers it

How deep it goes
Explains the interval-search rationale but stops short of implementation details, benchmarks, and formal complexity analysis.
Examples
Uses interval lookup and large-list membership as practical cases for comparing search strategies.
What it assumes
Assumes familiarity with Python lists, sets, dictionaries, membership tests, and ordered values.
What you can do after
Evaluate whether ordered-list bisection fits an interval search better than repeated set or dictionary lookups.
How it connects
Connects interval search with ordered lists and contrasts it with set, dictionary, and linear membership search.
Cover of Fast Python: High performance techniques for large datasets
liveBookmanning.com
Read Fast Python: High performance techniques for large datasets on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Fast Python: High performance techniques for large datasets. The section links point to the parts of the book it draws on.