Binary Search in JavaScript

binary search in javascript code

“Binary search” is a computer science term used in programming and software engineering. It is a way of determining if a value exists in an ordered data set. It’s considered a textbook algorithm. It is useful because it reduces the search space by half on each iteration.

Imagine we are asked to search for an integer in an array that is sorted in ascending order. The challenge is to return the target number’s index.

binary search

We could use a built in JavaScript function indexOf():

var search = function(nums, target) {
    var answer = nums.indexOf(target);
    console.log(answer);
    return answer;
};
console.log(search([-1,0,3,4,5,9,12], 5)); // returns '4'

But that is an abstraction, which can be slow and expensive. Instead, we should implement our own binary search code.

Binary Search Implementation

Binary search starts in the middle of a collection, and checks if that is the requested term. The initial middle position is determined by taking the length of the array and dividing it by two. If the array has an even number of elements, then the ‘halfway position’ is considered close enough. I use a JavaScript Math function to round down, making sure I am not left with a decimal floating number:

cursor =  Math.floor( ((left + right) / 2) ); // about the middle

If the search term is not found, the position (the cursor) is moved. Since the collection is ordered from smallest to largest we know which direction to move the search cursor. If the target is less than the current value, we shift one to the left. If the target is greater than the current value, we shift two to the right.

This continues until the target query is found. That sequence is ran inside of a loop. The loop repeats while the left boundary is less than (or equal to) the right. The search cursor’s index is changed by adjusting the left or right bounds. Once adjusted, the cursor is recalculated on the subsequent iteration.

var search = function(nums, target) {
    var left = 0; // first element, initial left boundary
    var right = nums.length;
    right = right - 1; // last element, initial right boundary
    var cursor = 0;
    while(left <= right){
        cursor =  Math.floor( ((left + right) / 2) ); // about the middle to start
        console.log(cursor + ": " + nums[cursor]);
        if(nums[cursor] === target){
            return cursor; // query found!
        }
        if(target < nums[cursor]){
            right = cursor - 1; // move cursor to the left by one
            console.log("cursor moved to the left  by one")
        }else{
            left = cursor + 1; // move cursor to the right by two
            console.log("cursor moved to the right by two")
        }
    }
    return "false"; // not found
};
console.log(search([-1,0,1,2,3,4,5,6,7,8,9,10,11,12], 10));

The above code starts to search in the central location, nums[6] == 5. Look at the output below to see how the cursor moves until it finds the target value of 10 (at a zero-based index of 11):

binary search output

This algorithm has an O(log n) runtime complexity. That Big-O notation describes how it would scale as the input increases. Imagine an array with thousands of elements. O(log n) means that the time to execute this code will increase linearly only as the number of input items increase exponentially. That means our code is performant and efficient.

Why did the computer scientist use binary search to find his lost pencil? Because he wanted to reduce the search space by half every time he checked a desk drawer!

Square root algorithm using binary search

Another implementation example of using binary search in a JavaScript function is to calculate the square root of a number. Now, of course, Javascript has a built in Math.sqrt() function that is highly performant compared to any custom code we will write. But, it is a good exercise to think about how this works.

The square root of a number is a value that, when multiplied by itself, gives the original number. To solve for it when given an input, we are going to take a guess at what the answer (square root) is, starting with itself divided by two (giving us the midpoint between it and zero). We multiply that midpoint by itself to check our guess. It will only be correct on the first iteration if the input is the number four (four divided by two is two; two times two is four). Otherwise, we will move the cursor (halving the search range) to either the left or the right, depending on if the square of our guess is larger or smaller than the original input.

The concept of “moving the cursor” helps to visualize how the binary search algorithm zeroes in on the square root by iteratively narrowing down the search range based on the comparison of the square of the midpoint to the target number.

I accounted for two special cases in my code. For negative numbers we return false because negative numbers have imaginary square roots. For numbers smaller than one we set the range’s end to one because the square root of a fraction is larger than the fraction itself. Additionally, I set a precision threshold (0.0000000001), because some numbers have square roots that are irrational.

function binarySearchSquareRoot(n, precision = 1e-10) {
    if (n < 0) {
        throw new Error('Input must be a non-negative number');
    }

    let start = 0;
    let end = n;

    // If the number is less than 1, set end to 1 to handle fractions
    if (n < 1) {
        end = 1;
    }

    while (end - start > precision) {
        const mid = (start + end) / 2;
        const midSquared = mid * mid;

        if (midSquared === n) {
            return mid;  // Found exact square root
        } else if (midSquared < n) {
            start = mid;
        } else {
            end = mid;
        }
    }

    return (start + end) / 2;  // Return approximate square root
}

// Usage:
const number = 25;
const squareRoot = binarySearchSquareRoot(number);
console.log(`The square root of ${number} is approximately ${squareRoot}`);

Alternatively, the Babylonian algorithm can be  implemented to solve for square roots.

Additional References

https://delboy1978uk.wordpress.com/2018/02/06/binary-search-trees-in-php/
https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/

Look-and-Say in PHP

The look-and-say sequence is a series of integers. It can grow indefinitely. It is generated by reciting a number phonetically, and writing what you spoke numerically. Its popularity is attributed to famed cryptographer Robert Morris. It was introduced by mathematician John Conway. It looks like this:

1
11
21
1211
111221
312211
13112221

The first line would be pronounced as “one 1”, and then written as “11” on the second line. That record would be spoken as “two 1’s”,  giving us the third line “21”. The greatest individual symbol you’ll ever find in this consecution is a 3.

This topic has lots of trivia, variations, and history that could be dug up and expounded upon. Here, I’ll explain a solution written in PHP to produce this chain of numerals. The input will be the count of how many lines, or iterations, in the series to generate. Below is the code:

<?php

echo "Count And Say: \n";

function countAndSay($count=0){
	$value = 1; // initial seed
	for($i=1;$i<=$count;$i++){
		echo $value . "\n";
		$value = calcOutput($value);
	}
}
function calcOutput($value){
	$value = "$value";  // change it into a string, so we can iterate over each character
	$current = $value[0]; // first character
	$count = 1;
        $return = '';
	for ($i = 1; $i <= strlen($value); $i++) { // keep going until we get through the whole string
		if ($current != $value[$i] || $i == strlen($value)) { // found a different character, or end of the input string
			$return .= "$count$current";
			$count = 1; // reset count
			$current = $value[$i]; // set new current character
		} else {
			$count++;
		}
	}
	return $return;
}

countAndSay(7);

echo "\n\n";

?>

I separated my code into two functions. I think this is the best approach. As an exercise, see if you can figure out how to refactor it into one. This could help you to internalize the logic as you write it out for yourself.

The initial seed value is “1”, and that is hard-coded at the top. The for-loop iterates based on the count input parameter. That means the code circles back and re-runs, with updated values, until its internal count (represented by the variable $i ) matches the $count variable passed into countAndSay($count).

The code that we loop over outputs the current sequence value (starting with 1) as its own line (“\n” will output a new line in most programming languages) , and then calculates the next. The function that determines the next line of output, calcOutput($value), takes the current value as an argument.

The first thing we do is cast the integer value passed along into a string. This lets us refer to each character by index – starting at zero – and save it to a variable $current. We start a new $count, to keep track of how many times we see the same digit.

The next for-loop executes for the length of the $value string. On each loop, we check if the $current character we saved matches the subsequent one in that $value string. It is again referenced by index, this time based on the for-loop’s iteration count represented by the variable $i.

If it does match, one is added to the $count variable that is keeping track of how many times we see the same character is a row. If it doesn’t match (or we’ve reached the end of the input), the $count and $current number are concatenated to the $return element. At that point, the $count is reset to 1, and the $current value is updated.

Writing an algorithm to generate the look-and-say (also known as, count-and-say) sequence is a common coding puzzle. You might run into it during a job interview as a software engineer. As practice, see if you can simplify my example code, or even write it in a different programming language than PHP.

Who is Anthony Pace

Who is Anthony Pace?

I’m a software engineer and web developer. I was born in New York City, and love living here. Being creative, solving problems, and building things excite me. I believe that boredom is the enemy of happiness. Having new experiences is how I find inspiration.

Programming and computers are important to me. I spend a lot of time online. The internet has helped me to discover things that are now important parts of my reality. I love to be a part of the wave by creating content, technology, and experiences for the web. This aspect of my life lets me be artistic and scientific at once

Fitness

As a life-long athlete, fitness and health are important to me. I spend weekends running, and participating in races around NYC. This is when I have some of my best ideas. Exercise gives me the energy I need to tackle my goals. During my best workouts, I experience a sense of flow only matched when I’m absorbed deeply into a creative project. I also enjoy lifting weights and martial arts.

Media

I draw inspiration from a lot of different places. I listen to podcasts and audiobooks while commuting (but still often do read actual books). Twitter has become one of favorite resources for new content. Consuming media propels my own creative urges. My drive to turn the imagined tangible boldens as I see others do it. You can check out my blog to find out more about what excites me.

Traveling

The urge to explore precedes creative expression. Experiencing the culture of a strange place stretches the imagination. I travel a few times per year for work, attending conferences and exhibitions, doing marketing work and managing live educational events. I also find myself on long adventures during my off time. These journeys have afforded me opportunities to meet people from around the world and make great memories.

Events

Social gatherings are exciting. Concerts, meet-ups, parties, and conventions help me connect with interesting people. In connecting with others we grow. I enjoy live music and good food. I attend group meetings that focus on my professional interests. Even digital events in virtual worlds present entirely new landscapes for me to explore.