## Objective

Implement the binary search algorithm in JavaScript.

## Difficulty

## Description

Searching for a given item in an array is a quite common task. For instance, given the array `[1, 2, 3]`

, we might be interested in finding out whether it contains `4`

in it.

Programatically, there are two ways to search for a given item in an array.

One is the straightforward, simple, sequential approach which is used by all the predefined searching methods in JavaScript.

In this approach, we iterate over the entire array in search of the desired value. As soon as it is found, searching is ended.

The second way is an extremely clever, logical magic. It's called ** binary search**.

The name comes from the fact that searching goes by finding out the value at the middle of *two halved* subarrays.

In this method, the array is halved into two segments and it's determined where the given value would be by comparing it with an element in between the halved subarrays. At each step, a half segment is discarded, keeping search around the other half. This leads to an extremely quick search.

Shown below is a demonstration of how binary search would find the number `500`

in the array `[1, 2, 9, 20, 60, 100, 101, 200, 500]`

:

In this exercise, you have to create a function `binarySearch()`

that takes in two arguments * val* and

*, as shown below:*

`arr`

```
function binarySearch(val, arr) {
// Code goes here
}
```

and returns back `true`

if * val* exists in

*, or otherwise*

`arr`

`false`

. The function should use binary search to find *in*

`val`

*.*

`arr`

## Hints

#### Hint 1

Use two variables, `start`

and `end`

, to keep track of the indices of the starting and ending elements of the subarray under inspection.

#### Hint 2

Compute the index of the middle element of the subarray using the expression `Math.floor((start + end) / 2)`

.

## New file

Inside the directory you created for this course on JavaScript, create a new folder called **Exercise-31-Binary-Search** and put the .html solution files for this exercise within it.

## Solution

The solution to this exercise boils down to implementing the binary search algorithm in JavaScript.

Let's break it down into simple steps...

At each step in a binary search, we are concerned with a subarray of the main array. First of all, note that there is no need to actually slice out subarrays from `arr`

. We could model them using two indices — one specifying the position where to begin the subarray while the other one specifying the position where to end the subarray.

Let's call these ** start** and

**, respectively.**

`end`

At the start of the search, since we are concerned with the whole array, `start`

would be `0`

while `end`

would be `arr.length - 1`

(the last index of `arr`

).

Given these two indices to represent the concerned segment of `arr`

, our next step is to read its middle element's value and compare that with `val`

.

How do we determine where is the middle element? For instance, given the indices `0`

and `2`

, what would be the index of the middle element? `1`

? Yes.

Given the indices `7`

and `9`

, what would be the index of the middle element? `8`

? You're right. Well done.

If you're a math guy, you'd know that computing the middle value of two numbers `a`

and `b`

could be simply done by `(a + b) / 2`

. However, this expression could sometimes give us a decimal number which won't be suitable as an array index.

For instance, given the indices `0`

and `3`

(let's say to denote the array `[1, 3, 5, 10]`

), `(0 + 3) / 2`

would be equal to `1.5`

.

Now, as we know, there is no such index in the world of arrays. Hence, it turns out that we couldn't directly rely on the return value of this expression.

*Any other options? Anything else we could do to this expression?*

Definitely yes! We could floor it.

So for instance, given the indices `0`

and `3`

, as before, `(0 + 3) / 2`

would give `1.5`

and then `Math.floor(1.5)`

would give `1`

.

This index coul be used as the middle of the array, though technically, it won't truly be the middle (after there is no middle element of an array with an even number of elements!).

To summarise this discussion, in order to compute the middle position of the concerned subarray denoted by the indices `start`

and `end`

, we simply use `Math.floor((start + end) / 2)`

. Let's call this as ** i**.

Moving on, with the index of the middle element in hand, the next step is to read `arr[i]`

.

There are 3 possibilities:

`arr[i]`

is less than`val`

. This means that val must be to the right side of this element, likewise in this case, we simply discard the left segment, including the value`arr[i]`

.`arr[i]`

is greater than`val`

. This means that`val`

must be to the left side of this element. Likewise, we simply discard the right segment, including`arr[i]`

.- When the above two conditions fail, it's known for sure that
`arr[i] === val`

. Hence, in this case, we exit the search operation and return`true`

.

The *'discard'* step above is accomplished simply by changing `start`

or `end`

to a value that limits us only to the concerned segment.

`start`

is set to the position after `i`

while `end`

is set to the position before `i`

.

Now, since all the steps mentioned above are to be repeated for each new concerned segment of `arr`

, they would go inside a loop.

But the question is: *what condition to set for the loop?*

Hmm. This is a good question.

In the worst case, a binary search algorithm would keep on halving `arr`

in search of `val`

uptil the point when the concerned subarray has a length of `1`

.

And it wouldn't even stop here. It would check that value as well, and if that's not equal to `val`

, it would reposition the subarray. This final repositioning leads to `start`

becoming greater than `end`

, which signals that `arr`

has been exhausted and hence, the loop should end.

In other words, as long as `start`

is less than or equal to `end`

, looping should go on.

Altogether this gives the following code:

```
function binarySearch(num, nums) {
nums.sort(function(a, b) { return a - b; });
var start = 0;
var end = nums.length - 1;
while (start <= end) {
var i = Math.floor((end + start) / 2);
if (nums[i] < num) start = i + 1;
else if (nums[i] > num) end = i - 1;
else return true;
}
return false;
}
```

`binarySearch(10, [1, 5, 10])`

`binarySearch(500, [1, 2, 9, 20, 60, 100, 101, 200, 500])`

`binarySearch(10, [1, 2, 9, 20, 60, 100, 101, 200, 500])`

`binarySearch(10, [10])`

`binarySearch(10, [])`

## Time complexity of binary search

There is a diverse topic in computer science known as ** asymptotic algorithmic analysis**, where we study the running times of different algorithms (and even their memory consumptions, but that's not important for now).

There is quite a decent amount of math involed in it, although not something like rocket science. Asymptotic analysis is an extremely useful tool for analysing the performance of various algorithms for a given problem.

Let's have a look over the time complexities of the two searching approaches we saw above, namely linear search and binary search.

The running time of linear search, also known as sequential search, is denoted as ::O(n)::, while that of binary search is denoted as ::O(\log_2n)::. For now, it's not important to understand the details of these notations. We'll just suppose that given an array `arr`

with length ::n::, each expression returns the number of milliseconds taken to search for `val`

in `arr`

in that respective approach.

That is, linear search takes ::n:: milliseconds and binary search takes ::\log_2n:: milliseconds.

Now, let's say that ::n = 100,000,000::, which is not surprising these days when datasets are humongous!

Linear search would take:

However, binary search would take:

See the difference? *It's enormous, jaw-dropping, insane, and what not!*

The implementation using linear search would take over a day to complete, whereas the one using binary search would be ready with an answer even faster than the blink of an eye!

This is the magic of binary search. No matter how enormous the main array becomes, binary search would complete in a very short span of time.

Now you might think that is binary search actually used out there. A big big yes! It's used in almost every application that deals with hefty amounts of data on which searches ought to be conducted frequently.

*The world of computer science is just huge!*