Binary Search - Sequentiell

Have you ever wondered how the Binary Search Algorithm works? - In this blog post I'll show you the main concepts of the BinarySearch-Algorithm, first the sequentiell and later on the rekursive algorithm.

The Idea

The idea behind Binary-Search is really simple. Suppose you had an telephone book and wanted to search for a number in this book. The value would be the number and the key would be the name.

Where would you begin to search? - For example if you search for John Does telephone number. Suppose the telephonebook has no index. The only way you know where you are in the alphabet is, if you look at an specific entry in the book.

Well, I would begin somewhere at the beginning because I know 'D' is relatively at the beginning. But for our algorithm we don't really need this. It's much more simple:

Steps

• Determine the lowest index and the max index
• get the middle index
• check if the item at the middle index is our search key, if it's our key, return the key
• if the key is less our item at the middle index set the highest index to the left item of our middle index
• if the key is bigger than our item at the middle index set the lowest index at the right item of our middle index
• repeat

In telephone book analogy you would search something like this:

• first open the Book right at the middle, look at the entry in the middle if the name your searching for is the item you were looking for you're happy. You found the telephone number
• if the name you're looking for is less the middle entry - search from the beginning to the left item - otherwise from the right item from the middle item to the max item
• for example, if you know John's telephone number is in the right part of your opened telephone book. Take the right part, open the middle page from this part and look at the name, if it's the name you've found it. Otherwise you repeat until you're done.

Flowchart of the BinarySearch Algorithm

Java Code

public static int binarySearch(int key, Integer[] sortedList) {
    int low = 0;
    int high = sortedList.length-1;

    while (low <= high) {
        int mid = (high+low)/2;

        if(sortedList[mid] == key) {
            return mid;
        } else if(key < sortedList[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

Step by Step

    int low = 0;
    int high = sortedList.length-1;

Define the lowest index and the highest index.

while (low <= high) {
...
}

We do the following while the lower border is smaller and equal the highest border

int mid = (high+low)/2;

We choose the middle Index.

if(sortedList[mid] == key) {
    return mid;
} else if(key < sortedList[mid]) {
    high = mid - 1;
} else {
    low = mid + 1;
}

Here we decide if we go 'left' or 'right'. First we check if the item at our middle position is our item we're looking for. Then if this is not the case we check if the key is smaller than our item or bigger than our item. If it's smaller we we set the high index to the left item from our mid item. If it's bigger then we adjust ower lower index.

This repeats until our middle item equals our key.