Exercise: Binary Search

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.

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 end, respectively.

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:

1. 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].
2. 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].
3. 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, [])

Live Example

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!