Rethinking Binary Search: Improving on a Classic with AI Assistance
summary
Proposes a concrete rewrite of STL binary-search primitives: implements a bounds-leaning search (cut 1/2 then 1/4) plus a left-leaning upper bound and optional galloping, generates C++ code, math and empirical benchmarks with ChatGPT assistance, and plots with WolframAlpha. Shows savings of about 0.5–2 comparisons on average (≈5–10% speedup at N≈1,000,000), small worst-case regressions, and clear wins when many queries fall outside the stored range; all changes are measured, not just hypothetical.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 11:48Classic binary search
- 22:03Expected comparisons
- 29:13Out-of-bounds searches
- 37:04Extreme out-of-bounds optimization
- 42:04Bounds-leaning binary search
- 45:38Improving equal range search
- 55:11Summary and AI assistance
related talks
01h 33mRobots Are After Your Job: Exploring Generative AI for C++
34mAlgorithms to live
36mBeyond Grep: Search for Reliable Coding Agents
32mRetrieval Augmentation and Semantic Search at Scale
32mUnder the Hood: Key Algorithms Powering Vector Search
43mOpenSearch and the Path to a Trillion-scale Vector Database
39mFrom Search to Insight: Leveraging OpenSearch for Scalable, AI-Driven Search Experiences
37mLearned Indexes: a New Idea for Efficient Data Access #bbuzz