Binary Search

by Mirabelle Jones

Binary search is a more advanced searching algorithm than linear search that only works for sorted data. Don’t let the word “binary” throw you off: you don’t need to know what 01101000 01101001 means in order to understand this search method!

In simple terms, in a binary search we cut our search area in half each time by choosing a middle point. Then we check to see if our value is larger or smaller than that middle point. If it’s larger, we next search between our middle point and the largest value. If it’s smaller, we search between the middle point and the smallest value. So each time we’re cutting our search area in half, narrowing in on where our value is! As you can probably guess, this only works with data that’s sorted because otherwise we can’t tell where our value is by comparison.

In a binary search, we pick a middle point then see if our number is larger or smaller than this number. If it’s smaller, then we update our search area to be between our mid-point and that smallest value. In this way we narrow the window of our search until we find our value!

You can see how this might be faster than linear search, because we’re cutting our search area in half each time. See the animation below for an example of this.

Graphic from penjee.com where you can learn Python!

Scenario

We actually use binary search a lot in everyday problem solving and navigation without even thinking about it. For example, say we’re staying at a hotel in room 333. We probably know which floor our room is on by the first digit so we head up to the third floor. We get out of the elevator, but then which way do we turn? Right or Left? Luckily, there’s a sign that tells us rooms 350 and lower are to the left, rooms 351 and higher are to the right. So we go left because 333 is lower than 350. We head down a corridor but then we hit another split. A sign says rooms 325 and lower, to the left. Rooms 326 – 349 to the right. Right we go! In this way, we can zero in on where our room is without needing a map of the whole hotel.

Below is another real world binary search example of finding a book in a library:

Here’s a similar example of a real life binary search: looking for a book in a library.
Video by Computer Science Tutorials.

In pseudocode (i.e. not working code), our search might look like this:

function findOurRoom(allRooms, ourRoom) {
    startingRoom = 300;
    endingRoom = 399;
    middleRoom = (startingRoom + endingRoom) / 2;
    while(allRooms[middleRoom] != ourRoom and startingRoom <= endingRoom) {
        if(ourRoom < allRooms[middleRoom]){
            endingRoom = middleRoom - 1;
        } else {
            startingRoom = middleRoom + 1;
        }
        middleRoom = (start + end) / 2;
    }
    if(allRooms[middleRoom] == ourRoom){
        return middleRoom;
    }
    return -1;
}

Wow! OK that seems a little more complex now that we’ve put it into pseudocode, but it’s still the same basic logic as our hotel room search from before. Let’s go over it line by line to see how it’s actually working.

We start by creating our function findOurRoom. This function has to know what it’s searching for (our room) and where (out of all the rooms on the third floor) so we give it these two items as parameters:

function findOurRoom(allRooms, ourRoom) {

When we’re doing a binary search, we’re trying to narrow down where our value is by looking at it relative to other values. So we’ll need to have a way of storing what those other values are. In our hotel room example, we enter floor 3 and the rooms are perfectly divided in half. So we need a way of identifying where we are (a midpoint) and then a way of identifying the smallest room on the floor (300) and the largest (399) which will be the window we’re searching within. To keep track of these, we’ll create variables to store our starting room, ending room, and middle room.

  startingRoom = 300;
  endingRoom = 399;
  middleRoom = (startingRoom + endingRoom) / 2;

OK great! Now we have values to compare so we can see where we are in relation to them. But the next line is maybe a little confusing:

while(allRooms[middleRoom] != ourRoom and startingRoom <= endingRoom)

Here we’re using a while loop which is a way to do something over and over again without writing a ton of code. All a while loop does is say “while (some condition is true) keep doing _______.” When the condition isn’t true, it keeps executing whatever is inside of it. Here we’re saying: while the room we’re starting at (the middle room) isn’t our room and the starting room is less than or equal to the ending room, let’s keep looking for our room. That second part is necessary in case our room (somehow) isn’t even in the hotel. Why would that ever be the case? Who knows, maybe they accidentally skipped a room or eliminated room 313 for bad luck? Or maybe we’re in some strange Murakami novel? Who knows? Moving right along, the next section is the heart of our while loop:

if(ourRoom < allRooms[middleRoom]){
            endingRoom = middleRoom - 1;
        } else {
            startingRoom = middleRoom + 1;
        }
        middleRoom = (start + end) / 2;
    }

So here we’re checking to see: is our room number less than our mid-point or greater? In other words, do we go left or right? If we go left, then our new “ending room” will start at where we are minus one (because we know we’re not at our room, right?). And if we go right, then we set our starting room to be our new middle room plus one (again, because we know the middle room is not our room). Then we reset our midpoint to be halfway between our new largest value and smallest value as our new section to search!

if(allRooms[middleRoom] == ourRoom){        return middleRoom;    }

If we find our room (meaning we’ve zoned in on it by making it the midpoint) we return where it’s located… Or in real life use our keycard to get into it for some well-deserved relaxation in the tub with some potato chips! But wait, what’s this?

return -1;

You’ll notice this looks familiar from linear search if you’re coming from that example. If not, basically this is saying “if we never find our room” (for example, if it doesn’t exist on this floor… an eerie possibility we should accommodate I suppose) return -1. This allows us to escape our loop and maybe head down to the lobby for a new room assignment… Hopefully they’ll throw in a free ticket to the brunch buffet for the trouble.

So that’s pretty much it! It seems a lot more confusing in code than it is in our everyday process (thank goodness we don’t have to be consciously aware of every step in our thinking, huh?).

Try some of the examples below if you’d like to experiment more with the code or feel free to move on to the next section (sorting algorithms).

If you’d like to learn more about binary search including how to implement it in real code, check out the sections below.

Big O Complexity

Best Case: O(1)

Example: our room is the first one outside of the elevator!

Worst Case: O(log n)

Our room is pretty much anywhere else so we have to continue to search until we find it.

Visualizations

Pseudocode

1. Create a function that accepts an array (the list of numbers we're looking through) and a value (what number we're looking for).
2. Create three variables that point (pointers, if you will) to the start, middle, and end of the search window. 
3. Create a while loop and set the condition to be while the start comes before the end.
4. Update our middle value to be halfway between start and end each time through the loop.
5. If the number we're looking for is our middle, return it!
6. Otherwise, check to see if the number we're searching for is higher or lower than our middle.
7. If our number is higher, change our middle value to be our new start value plus 1.
8. If the value is lower, change our middle value to be our new end value minus 1.   
9. If you never find our number, return -1. 

Code Examples

Javascript

function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

Sample Problems

Come back soon for these!

More Resources