Binary Search Explanation and Implementation

Explained

In this article, we will learn about an efficient searching algorithm for finding an item from a sorted list of items, which is a binary search. We label this algorithm as an efficient algorithm because the running time of this algorithm in the worst-case scenario is \({\displaystyle O(\log n)}\) (the logarithm base-2 of \(n\)) which is far better than the linear search, make sure that you already read this article to learn about time complexity before we proceed.

The binary search usually used to find a particular item in a sorted array, it works by comparing target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. For example, we have an array which is a really big phone book with 1,048,576 phone numbers and we want to find out one particular number. If we do it in linear search, which takes the \({\displaystyle O(n)}\), in the worst case the computer might have to examine all over 1,048,576 numbers. However, if this phone book is already sorted, we can implement the binary search to find this number, it would examine just \({\displaystyle O(\log 1048576 ) = 20}\) numbers, even in the worst-case and average-case (basically average is considered as the worst-case), but if you are lucky enough, you can find the number you’re looking for by this one search, who knows? and this is the best case in the binary search which takes \(O(1)\).

See a huge difference?

In order to implement the binary search, first, we should take a look at an example about the Guessing game that we’ll use binary search to guess the number, you need to guess a number between 1 and 100, let’s say that the number you need to find is 27 (but pretend you don’t know this number is 27 🙂 ), begin with the middle and after each guess, the computer will alert you whether the value you guess is too small or too big.

So, the first thing we do is choose the middle one, which is \( \frac{\left(1+100\right)}{2}=50.5 \), because the result is not an integer, simply we just need to round down to the closest integer, which is 50.

After we guess 50 is this number, the computer tells us this number is not correct and yelling the number we need to find is smaller than this, then we can eliminate the part from 50 – 100 and focus on the rest part, again we need to find the middle of this array from 1-49, which is \( \frac{\left(1+49\right)}{2}=25\)

We’ve guessed the number is 25, but again, the computer gives us an alert that it is not quite the correct number, it says the number is higher, then again we forget the part from 1-25 and find the middle of the 26-49, which is \( \frac{\left(26+49\right)}{2}=37.5 \) then the value now 37.

37 still not is the desired number, then we do the previous steps again and again, which as follow:

\(\frac{\left(26+36\right)}{2} = 31 \)
\(\frac{\left(26+30\right)}{2} = 28 \)
\(\frac{\left(26+37\right)}{2} = 26.5\) then 26 is the value we want to point at:

But at this point the computer will alert you a different message that the number you guess is smaller than the desired number, then we need to set the min value to the one larger, which is 27, but we already eliminated every other, then 27 is the final guess for the number.

As a whole, the procedure for finding a number in Guessing game using the binary search can be summed up as below:

Let’s set \(min = 1\) and \(max = n \)
Guess the average of \( max\) and \(min\), rounded down so that it is an integer.
If this average number is the right number, then stop. You found it!
If the guess was too low, set \(min\) to be one larger than the guess.
If the guess was too high, set \(max\) to be one smaller than the guess.
Go back to step two.

As you can see, with the Guessing game example below, if we guess the number by guessing each number and increase by one after each subsequent search by using a linear search, we have to guess 100 times in the worst case if this number is 100. Nonetheless, with binary search, we just have to maximumly search \(\log _2\left(100\right) = 7\) guesses.

Implementation

Although JavaScript language, as well as many other languages, already have some built-in functions to find the particular element and also its index in an array. Yet, for the purpose of this article, we are going to implement the binary search for ourself which takes an array as an input, the number of \(n\) elements and the \(target\) value we want to find and return the \(target\) index. We also can implement the binary search function with recursive style, but in this article, I just introduce the general imperative style. First, we don’t dive right away in a particular language, instead, we will write the pseudocode – which mixes English with features that you see in programming languages. When you understand the pseudocode, you can implement the algorithm in your favorite language with no barrier:

Let’s set \(min = 0 \) and \(max = n – 1\)
Compute the \(guess\) as the average round down to an integer if necessary.
If \(array[guess] = target\). Then stop, you’ve found it, return the \(guess\), which is the index.
If the \(guess\) was low, then increase the \(min\) by one, that is \(array[guess] < target\) then \(min = guess + 1\).
Otherwise, if the \(guess\) was too high, set the \(max = guess -1\)
Go back to step 2, if \(target\) not found, return -1.

Now, let’s step-by-step implement binary search in JavaScript for searching a particular element. First of all, we create a function named \( binarySearch \), which takes 2 parameters \(array, targetValue\), and we initialize 3 variables, \(min = 0\) \(max = array.length – 1\) and \(guess\):

function binarySearch(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
}

Next, we will create a loop to do work for us, in this case, is the while loop, its job is to keep repeating the piece of expressions inside it until the certain condition is reached, in order to do the binary search, the \(array\) always needs to be sorted, so it will be the condition for this loop to run properly. Inner this loop, we assign the value of \(guess\) to the average value between the \(min\) and \(max\), round down to closest integer if necessary, and the value of \(guess\) will be changed after each iteration, if the \(array[guess] == targetValue\) then return this index:

while (min <= max) {
        guess = Math.floor((min + max) / 2);
        if (array[guess] === targetValue) {
            return guess;
        } else if (array[guess] < targetValue) {
            min = guess + 1;
        } else {
            max = guess - 1;
        }
}

Otherwise, if the value we are looking for doesn’t exist in this array, simply we return -1.

return - 1;

Put all the pieces together, now we have the complete function to find an index of a particular element in an array:

function binarySearch(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while (min <= max) {
        guess = Math.floor((min + max) / 2);
        if (array[guess] === targetValue) {
            return guess;
        } else if (array[guess] < targetValue) {
            min = guess + 1;
        } else {
            max = guess - 1;
        }
    }
    return -1;
};

Calling this function with a specific array and a target value to make sure it works properly:

console.log(binarySearch([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
], 29));

You can run this code with your favorite editor, for example, Visual Studio Code or Atom, Vim, etc…In my case, I’m using Visual Studio Code with the Code Runner Extention, I can run JavaScript code easily by specifying the piece of code and click to the run button that I point here:

Also if you are using a browser such as Chrome, Brave, Opera to read this article, you can run directly this code on your browser by typing the keystroke Ctrl + Shift + J on Windows, or Command + Option + J on macOS:

Let’s again break down what happened with this code:

First, we create the function called \(binarySearch\) which takes the array with all the prime numbers which are less than 100 and the target value we want to find here is 29.
Inside this function, we declared a few variables, \(min = 0\), \(max = array.length – 1 = 25 – 1 = 24\).
The while loop will run if the condition \(min <= max \) is satisfied, and \(guess\) is the index of the element we are looking for, we also can see some conditions inside this loop, which reflect to the pseudocode, if \(array[guess]\) is the \(targetValue\) then we return it, if [guess] was too small, increase the \(min\) value, otherwise we decrease the \(max\) value by one.
But finally we still couldn’t find the value when there is just only one element left, then return -1.

0 0 votes

Article Rating

Facebook Tweet

Binary Search Explanation and Implementation10 min read

Explained

Implementation