# Binary search: algorithms explained (3 of 8)

Binary search is an important search algorithm for software engineers to know because it provides an efficient way to find items in a sorted list, and it demonstrates concepts that are fundamental to many other algorithms

Below, we’ll explain what exactly binary search is, how it works, and when and how to implement it. We’ve also included a handy cheat sheet so you can check its space-time complexity at a glance.

Here’s an outline of what we’ll cover:

Let's get into it.

## 1. Binary search basics

In order to crack questions about binary search, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.

### 1.1 What is binary search?

Binary search is one of the fastest search algorithms because it halves the search space with each iteration. Binary search requires an ordered set that also has constant access times. This means that, of all the basic data structures, only sorted arrays are suitable for binary search.

Here’s how binary search halves the search space with each iteration:

1. Find the middle element in the current search space. If this middle element is the target element, then return its index and stop the search.
2. Else, determine whether the target element is to the left or right of the middle element, and reduce the search space to that half containing the element.
3. Repeat the process on the halved search space: identify the middle element, return its index if it’s the target element, or determine which half of the search space the element will be in, and reduce the search space to that half.
4. This search will continue until the target element is found or as long as there are items in the search space. If the search space contains no items, the algorithm has failed to find the target element in the array, and returns -1.

Let's search for the number 7 in the following sorted array, tracing the first three iterations:

On the first iteration our search space runs from index 0 to index 6, which makes 3 the middle index. The value at index 3 is 5 – this tells us that our target value 7 must be somewhere in the upper (or right) half of the array. We reduce the search space to the right half from index 4 to index 6, making index 5 the new middle. Index 5 has a value of 9, meaning our target value 7, being less than 9, must be in the left half of this reduced search space. So we halve the search space again to the left half, from index 4 to index 4 – which also makes index 4 the new middle. This new middle has the value of 7 that we are looking for, so we found our item at index 4.

#### 1.1.1 Use cases for binary search (Java, Python, C++)

Binary search has a limited set of use cases:

• It is used to quickly find the index of an item in a long list. For example, a database index might contain 1,000,000 items. A binary search can find the item within 20 steps (log2 n time).
• This can be extended to finding ranges too. Given a sorted array of net wealth, all the billionaires can be found by determining the index of the first billionaire value. The range from this index to the end of the list will be all the billionaires.
• It is also used to find the index for insert and delete operations on a sorted array.

#### 1.1.2 Example implementation

The implementation for binary search is straightforward, however there are some details we have to pay careful attention to.

We need to be careful when calculating the midpoint. It is tempting to calculate the midpoint as (beg + end) / 2, but this approach has two issues: First, adding the two numbers together can result in an overflow if they are both large. To avoid this, we add half the space size to the beginning. Second, we have to ensure mid is an integer value to be able to use it as an index. In Python the double forward slash (//) can be used to perform integer division. In other languages, a math “floor” routine can be used.

We also have to be careful of the while condition. If we specified beg < end (not including the end), then our example earlier would have failed to find the 7. The search space shrunk to one item on the third iteration, making the beginning and end the same item. To avoid this error, we use beg <= end.

#### 1.1.3 How binary search compares to other algorithms

In terms of speed, only hash maps are faster than binary search, since hash maps can determine whether an item is in a set in constant time. However, hashing cannot tell us the next smallest or biggest item based on the item searched for. Hashing also cannot give us all the items in a given range, or the smallest or biggest item in the array.

A drawback of binary searching is that it requires a sorted array, because sorted arrays have linear insert and delete time complexities. The alternative is unsorted arrays with constant insertion and deletions, but with linear search time. Even though linear searching does have excellent locality of reference for the CPU cache, this locality is not enough to out perform binary search.

A binary search tree (BST) offers better insertion and deletion times, but BSTs can become degenerate (when every parent node has just one child node), which reduces searching time to linear. Balanced trees are a solution to keep search time to log_2 n, but finding ranges in a balanced tree is harder, and finding the smallest or largest element is no longer constant time.

## 2. Binary search cheat sheet

### 2.2 Cheat sheet explained

The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.

The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for binary search). Binary search is related to several data structures, which are also included in the cheat sheet.

#### 2.2.1 Time complexity

As the search space is halved with each iteration, the time complexity of binary search is log_2. In the worst case, we won't find our item and the search space will shrink to size zero (0) once all possible iterations have been completed, giving a complexity of O(log_2 n). On average, some iterations are completed, reducing time to O(log_2 n). At best, the item we are looking for might be at the middle index, for O(1).

Finding the smallest or biggest item in a sorted array is O(1) and finding values in a range is O(log_2 n).

#### 2.2.2 Space complexity

The algorithm only needs to store the beginning and end indices of the search space, whether ten items or a million items are being searched, giving binary search a space complexity of O(1).

#### 2.2.3 Related algorithms and data structures: arrays and binary search trees

Binary search requires the array it searches to be sorted. Sorted arrays only have constant time insertions when inserting at the end of the array. When inserting anywhere else in the array, all the items after the insertion point have to move one index right to accommodate the new item. This results in an average insertion time complexity of O(n).

Similarly, deleting the last item in a sorted array is constant. But deleting from anywhere else in the array requires all the items after the deletion point to move one index left to fill the gap of the removed item. This also results in an average time complexity of O(n) when deleting.

When inserting and deleting times are a concern, a binary search tree (BST) can be used. Searching a BST is much like binary search:

1. Search starts at the root node. If the current node is the target value, it is returned and the search is stopped.
2. Else, if the target value is less than the current node, the search is continued on the left subtree. If the target value is greater than the current node, the search is continued on the right subtree.
3. These steps are repeated until the target value is found or as long as there are more subtrees, else return -1.

In this way, moving down each layer of the tree is like the iterations of a binary search. Let’s take a look at an example, searching for 7 again:

We start with the root node, which has a value of 5. This is not the 7 we are looking for, and since 7 is bigger than 5, we go to the right subtree. The value of the current node on the right subtree is 9 – not the 7 we are looking for, and as our target value is smaller than 9, we go to the left subtree. The leaf of the left subtree is compared to our target value 7, and since they match, the leaf node is returned.

Just like our array search, the search space is halved with each iteration for a time complexity of O(log_2 n). But adding a node with a value of 4 would be straightforward, as it would be the right-hand child of 3, giving insertion constant time.

## 3. How to prepare for a coding interview

Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only binary search, but also the rest of the relevant algorithms and data structures. Check out our guides for detailed explanations and useful cheat sheets.

Algorithms explained:

Data structures explained:

### 3.2 Practice on your own

Once you’re confident in all of these, you’ll want to start working through lots of coding problems.

Check out the articles in our algorithms questions series for practice on the most important algorithms:

We also recommend working through our list of 73 data structure interview questions.

One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview.

It's also a good idea to work on a piece of paper or google doc, given that in the real interview you'll have to code on a whiteboard or virtual equivalent.

### 3.3 Practice with others

Of course, if you can practice with someone else playing the role of the interviewer, that's really helpful. But sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.

That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.

Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.

## Any questions about binary search?

If you have any questions about binary search or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!