Objective

Implement the binary search algorithm in JavaScript.

Difficulty

Easy

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