Beginning Algorithms

Chapter 9. Binary Searching and Insertion

So far, this book has discussed basic structures for storing and sorting your data, but it has only touched on some rudimentary approaches to searching the data.

Modern software applications often deal with enormous amounts of data, and being able to search that data efficiently is important. Being able to locate a particular patient's record quickly among tens of thousands of others can make or break an application. From now on, the chapters in this book focus largely on algorithms and data structures designed specifically for the efficient storage and searching of data.

Binary searching is one of the most basic techniques for efficiently searching through data in memory. Binary insertion is a variation on binary searching that enables you to maintain the data such that it can be efficiently searched.

This chapter discusses the following:

• How to perform binary searching

• Implementing a binary search using iteration and recursion

• Comparing binary searching with other search techniques

• Comparing binary insertion with other sorting techniques

Understanding Binary Searching

Binary searching is a technique for locating items in a sorted list. A binary search takes advantage of certain characteristics of sorted lists that a simple linear search doesn't. Indeed, whereas a brute-force linear search runs in O(N) time, a binary search runs in O(log N), assuming the data to be searched is sorted.

As you saw in Chapter 2, the simplest way to search an unordered ...