Binary Search in JavaScript

In this week's JavaScript lesson we're going to look at how to create a Binary Search function.

What is Binary Search?

Binary search is an algorithm that locates the index of a value in a sorted list, like an array. It accomplishes this task by splitting the list in half and comparing the value at the mid-point index to the search value. If a match is found, the mid-point index is returned.

If the value is not located in the middle position of the list, the middle position becomes the new start or end for the search, based on if the search value is higher or lower than the value stored in the middle index. If the search value is higher, the mid-point index becomes the new start index. If it is lower, it becomes the end index.

The search continues, looping until the search value is found in the list. If the search value is not found, a statement indicating this is returned.

Binary Search Syntax

In JS, we define a function (binarySearch) that takes a list and value as its parameters (list, searchNum).

Next, local variables are declared for the starting index (minIndex), end index (maxIndex) and mid-point index (middleIndex).

While the start index is less than or equal to the end index, the middle index is set to the value halfway between them, using floor to round down.

Then, we use nested conditional statements to compare the search value to the mid-point index value, and either return the index or set a new starting/end point for our search.

Finally, if the while loop ends without returning a value, we return a statement to the user indicating that the search value was not found in the list.

function binarySearch(list, searchNum) { var minIndex = 0; var maxIndex = list.length - 1; var middleIndex; while (minIndex <= maxIndex) { //set middleIndex to the index halfway between the endpoints middleIndex = Math.floor((minIndex + maxIndex) / 2); //check if middleIndex contains searchNum if (list[middleIndex] === searchNum) { return "Input " + searchNum + " located at index " + middleIndex; } else { //if the value at middleIndex is less than searchNum //set new min starting point at one greater than middle if (list[middleIndex] < searchNum) { minIndex = middleIndex + 1; } //else set the max starting point at one less than middle else { maxIndex = middleIndex - 1; } } } //if searchNum not found return searchNum + " not in list"; } var numberList = [6,10,18,15,2,13,0,7,8,17,1,12,11,5,14,3,16,9,4]; numberList.sort(function(a, b){return a - b;}); console.log(binarySearch(numberList,11)); console.log(binarySearch(numberList,15)); console.log(binarySearch(numberList,10)); console.log(binarySearch(numberList,19));

Binary Search Example

I created an unsorted array of integers from 0 to 18. I used the built-in sort method to sort the list. Though, as in Java, the sort method will convert integers to strings and sort them based on their leading digit. So, 20 would be appear before 3 in a list.

To avoid this, we must include a comparison function, similar to how we override compareTo in Java. This function, nested inside the sort, returns a negative value if the first number is less than the second, 0 if equal, and a positive value if greater than.

I fed the sorted list into the binarySearch function and included a search value outside of the range and you can see in the output below that the search found the correct indexes for the values that were in the list, since they match their indexes, and returned a statement indicating that 19 is not in the list.

Sources: I based my function syntax on information found on StackOverflow. I used the Ace editor to embed my code with help from QuickGrid. And, I executed my code using JSBin to show the output.