Binary search
Binary search is an algorithm that locates a target or boundary in an ordered collection by repeatedly comparing with a midpoint and halving the remaining search range.
Grokking Data Structures
Binary search locates an item in an ordered sequence by repeatedly eliminating the half of the remaining search range that cannot contain it.
- How it is used
- Finds a target in a sorted array by repeatedly excluding half of the remaining range.
- How deep it goes
- Works through boundary updates and a Python implementation, then derives time and space costs; flags first-occurrence handling without implementing it.
- Examples
- Uses a card-search scenario, a Python search method, and an unsuccessful search that progressively eliminates array elements.
- What you can do after
- Build it from scratch for a sorted array and choose it when frequent searches justify the cost of keeping elements ordered.
Grokking Algorithms, Second Edition
An algorithm that searches a sorted list by repeatedly narrowing the search interval and returns the position of a matching element or null when no match exists.
- How it is used
- Finds an item's position in a sorted list without checking every item, returning null when there is no match.
- How deep it goes
- Works through successive midpoint guesses and gives a complete Python implementation with search bounds and a missing-item return.
- Examples
- Uses dictionary lookup, a 1-to-100 guessing game, and a Python list searched for present and absent values.
- What you can do after
- Build it from scratch using midpoint comparisons and low/high bounds, then compare its running time with simple search.
Read how Grokking Algorithms, Second Edition explains binary search →
Bayesian Optimization in Action
Binary search is a divide-and-conquer search algorithm that repeatedly compares a target with the middle element of a sorted sequence and discards one half of the remaining search interval.
- How it is used
- Connects binary search to information theory, decision-making under uncertainty, and information-theoretic policies for Bayesian optimization.
- How deep it goes
- Defines midpoint comparisons and interval halving, then interprets them through entropy; stops short of detailed algorithm instruction.
- Examples
- Uses a 100-element sorted list, midpoint comparisons, target-location distributions, and expected posterior entropy.
- What you can do after
- Evaluate/understand midpoint queries as entropy-reducing decisions and relate binary search to entropy-based optimization policies.
Read how Bayesian Optimization in Action explains binary search →
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A binary search locates a value in an ordered, index-accessible collection by repeatedly comparing with the middle element and halving the candidate range.
- How it is used
- Uses ordered array access to replace exhaustive search when selecting an appropriate search algorithm matters for performance.
- How deep it goes
- Explains the halving process, range updates, termination, generic Swift implementation, and a performance exercise without formal proof.
- Examples
- Demonstrates sorted word lookup, Gene and Codon lookup, generic arrays, and timing searches across one million numbers.
- What you can do after
- Apply it via Swift by implementing and timing generic binaryContains functions on sorted arrays.
Fabulous Adventures in Data Structures and Algorithms
Binary search locates an ordered value by repeatedly comparing it with the middle element of a sorted collection and discarding half of the remaining search range.
- How it is used
- Uses sorted collections to accelerate membership, prefix lookup, and cumulative categorical sampling.
- How deep it goes
- Explains API result encoding, prefix iteration, complexity, and zero-weight ties, without deriving the search loop’s invariant.
- Examples
- Demonstrates a sorted word list and cumulative ladder heights for categorical sampling.
- What you can do after
- Apply it via C# List<string>.BinarySearch for membership and insertion-point-based prefix enumeration.
Read how Fabulous Adventures in Data Structures and Algorithms explains binary search →
Advanced Algorithms and Data Structures
Binary search is a search algorithm that repeatedly halves an ordered search range to locate a target or its insertion position.
- How it is used
- Uses ordered arrays and lists to accelerate lookups when updates are infrequent or separately manageable.
- How deep it goes
- Explains midpoint partitioning, sorted-array costs, and one-dimensional limits, while stopping short of implementation pseudocode.
- Examples
- Uses a phone book, sorted contacts, corpus terms, and a sorted-array operation table.
- What you can do after
- Apply binary search to ordered data and evaluate its lookup benefits against sorting and update costs.
Read how Advanced Algorithms and Data Structures explains binary search →
Julia as a Second Language
Binary search locates an element in an ordered collection by repeatedly comparing against the middle of a narrowing search range.
- How it is used
- Uses binary search to explain why sorted arrays can support efficient element lookup.
- How deep it goes
- Explains middle comparisons and range halving, then stops short of implementing the algorithm manually.
- Examples
- Demonstrates searching for 18 in a nine-element array using Julia's sorted-search functions.
- What you can do after
- Apply binary search through Julia's searchsorted functions on sorted arrays.
Read how Julia as a Second Language explains binary search →
Related concepts
- linear searchcontrasts with · Linear search is a search technique that examines candidates sequentially until it finds a match or exhausts the collection.
- logarithmuses · A logarithm is the exponent to which a specified positive base other than one must be raised to produce a given positive number.
- Kafka brokerused by · A Kafka broker is a server process in an Apache Kafka cluster that stores records and handles producer, consumer, and other client requests.
- sorted listuses · A sorted list is a sequence whose elements are arranged according to a defined ordering criterion.
- similarity searchkind of · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.
- divide-and-conquer approachkind of · Divide and conquer is a problem-solving strategy that decomposes a problem into smaller parts, handles them separately, and combines or completes their results.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.