Objective
Implement the binary search algorithm in JavaScript.
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 arr
, as shown below:
function binarySearch(val, arr) {
// Code goes here
}
and returns back true
if val
exists in arr
, or otherwise false
. The function should use binary search to find val
in 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-34-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 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:
arr[i]
is less thanval
. 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 valuearr[i]
.arr[i]
is greater thanval
. This means thatval
must be to the left side of this element. Likewise, we simply discard the right segment, includingarr[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 returntrue
.
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!