18
Faster Searching with Binary Search
In Chapter 17, we looked at linear search, a simple algorithm that works by scanning every item in a collection until it finds what it is looking for. While simple is good, the linear approach is slow. The more items you have, the longer it will take to find something. Its running time is O(n). There is a faster way to search, and that is the star of this chapter: the binary search.
In the following sections, we learn all about binary search, how it is implemented, its performance characteristics, and a whole lot more.
Onward!
Binary Search in Action
A binary search starts the same way as many great search algorithms do: with a collection of items (Figure 18-1).
FIGURE 18-1
Our collection of items
Get Absolute Beginner's Guide to Algorithms: A Practical Introduction to Data Structures and Algorithms in JavaScript now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
