# Binary Search Explanation and Implementation8 min read

## 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 (the logarithm base-2 of

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

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

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

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

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

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
and - Guess the average of
and , 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
to be one larger than the guess. - If the guess was too high, set
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

## 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

- Let’s set
and - Compute the
as the average round down to an integer if necessary. - If
. Then stop, you’ve found it, return the , which is the index. - If the
was low, then increase the by one, that is then . - Otherwise, if the
was too high, set the - Go back to step 2, if
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

```
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

```
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
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,
, . - The while loop will run if the condition
is satisfied, and 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 is the then we return it, if [guess] was too small, increase the value, otherwise we decrease the value by one. - But finally we still couldn’t find the value when there is just only one element left, then return -1.

## Leave a Reply