algorithms – Ant Pace Blog

March 9, 2023May 2, 2024

Binary Search in JavaScript

“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.

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):

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.

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/

September 23, 2022January 22, 2024

Memoization (Caching) and Recursion with JavaScript

A common coding challenge that you may encounter will ask you to write a function that returns the Fibonacci sequence, up to the nth number (which is provided as an argument). Below is a solution, along with some commentary about the topic. This challenge is a great exercise in problem solving.

Fibonacci numbers

The sequence starts with 0 and 1, and the next number in the sequence is always the sum of the previous two numbers. The first few terms of the sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811

Since this series follows a known pattern, we can write code to generate it up to a specified position.

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers.

These numbers were first described in ancient Indian mathematics. They are named after the Italian mathematician Leonardo of Pisa, also known as Fibonacci, who introduced the sequence to Western European mathematics in his 1202 book Liber Abaci. Fibonacci numbers are also strongly related to the golden ratio. In computer science, these numbers can be applied to programming algorithms related to search, data structures, and graphs.

Recursion

In programming, recursion is an important concept. Recursion is when a function calls itself. Writing code that generates the Fibonacci sequence requires recursion. Here is an example in JavaScript:

function fibonacci(n) {
    if (n < 2){
        return 1;
    }else{
        return fibonacci(n-2) + fibonacci(n-1);
    }
}
console.log(fibonacci(7)); // Returns 21

If you ask this function for 0 or 1 terms, it will simply return 1. It is the condition that will ultimately stop the recursion. Anything above that, it will have to call itself recursively. What exactly is happening there? This Stack Overflow thread does a great job stepping though the logic and illustrating each iteration.

When I decorate the code from above with console log statements and collect the results into an array, it becomes obvious:

function fibonacci(n) {
  console.log("Iterating on n = " + n)
  if (n <= 1) {
    console.log("n is: "+n)
    return [0, 1].slice(0, n + 1);
  } else {
    const fib = fibonacci(n - 1);
    console.log("fib is: "+fib)
    console.log("iterating on " + n)
    fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
    return fib;
  }
}

You can see it iterates all the way down, starting at the desired argument of term numbers, and ending with 1. Once it gets to the bottom, it starts going back up. On each subsequent round, it adds a new number to the result array by summing the previous two numbers.

I asked ChatGPT to rewrite this code for me, and this is how it was cleaned up:

function fibonacci(n) {
  if (n <= 1) {
    return [0, 1].slice(0, n + 1);
  } else {
    var sequence = fibonacci(n - 1);
    sequence.push(sequence[sequence.length - 1] + sequence[sequence.length - 2]);
    return sequence;
  }
}

This function has an exponential time complexity. It can be very slow for larger values of n.

Memoization and Cacheing

This challenge is often followed with a request to make it “more performant”. I mentioned above that our solution has “exponential time complexity”. Its algorithmic efficiency can be described as O(2^n) in Big O notation.

Every call (while n is greater than 1) results in two additional recursive calls, one with n-1 and another with n-2. Each of those calls then results in two more recursive calls, and so on, resulting in a binary tree of recursive calls.

The performance of this code can be improved by implementing memoization. Memoization is when we store the results of our function call. On subsequent calls, our application can look up answers it previously calculated without have to do the work again.

function fibonacci2(n, memo = {}) {
  if (n in memo) {
    console.log("we used the memo on: " + n)
    return memo[n];
  }
  if (n <= 1) {
    return [0, 1].slice(0, n + 1);
  } else {
    const fib = fibonacci2(n - 1, memo);
    fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
    memo[n] = fib;
    return fib;
  }
}
memo = {}
console.log(fibonacci2(7, memo));
console.log(fibonacci2(15, memo));

On each iteration we save the results to an array called memo. When we use the function, we first check to see if the answer we want is already stored in our cache. Our course, the work still needs to be done the first time around, but never again – making computation much faster in the future. You can see that my 2nd call can start where the results of the previous call left off:

By using memoization, this implementation of the Fibonacci function has a time complexity of O(n). Another way to improve the performance of our code, without using memoization, is to use a loop:

function fibonacci(n) {
  var sequence = [0, 1];
  for (var i = 2; i <= n; i++) {
    sequence.push(sequence[i-1] + sequence[i-2]);
  }
  return sequence;
}

The choice between memoization or a loop depends on the specific requirements and constraints of the use-case. While the time complexity of a loop-based solution is still O(n), it can be faster than the memoization approach for small or medium-sized values of n. If simplicity and readability are a higher priority, or if memory usage is a concern, a loop-based solution may be a better option.

Memoization is considered a “dynamic programming” technique. Dynamic programming involves solving sub-problems once and storing the results for future reference, which can significantly improve the efficiency of the overall solution.

July 9, 2022October 11, 2023

Palindromes in PHP

A palindrome is a word (or a string of characters) that can be read identically either forwards or backwards. Examples include:

racecar
madam
mom
level
civic
kayak
rotavator

The logic for determining a palindrome is simple. Take the input, reverse it, and then compare it to the original. PHP even has a built-in operation, strrev(), to reverse strings. We can write a function to judge if an input string is a palindrome:

function determinePalindromeWithReverse($value){
	$reverse = strrev($value);
	if($reverse === $value){
		echo "true \n";
		return true;
	}
        return false;
}

During an interview, for a role as a Software Engineer, I was asked “Given a string, determine if you can make it a palindrome by removing at most 1 character.”

To solve that challenge, I can loop through the string while increasing the value of a counter variable. On each iteration, I’d remove a single character (whose index is determined by the count), reverse the result, and then compare it.

function determinePalindromeWithReverseRemoveCharacter($value){
	$reverse = strrev($value);
	if($reverse === $value){
		echo "true \n";
		return true;
	}

	for($i=0;$i<=strlen($value);$i++){
		$first_half = substr($value, 0, $i); // first half of string
		$second_half = substr($value, $i + 1);
		$string_with_one_char_removed = $first_half . $second_half;
		echo "$string_with_one_char_removed \n";
		$reverse = strrev($string_with_one_char_removed);
		if($reverse === $string_with_one_char_removed){
			echo "true \n";
			return true;
		}
	}

}
determinePalindromeWithReverseRemoveCharacter("racecfar"); // true

I use PHP’s substr() function to get the each half of “the new string with one character removed.” The first division starts from the beginning (zero index) and continues up until the counter determined position (zero on the first loop, one on the second, and so on). The second part starts one step past the iterative count, and finishes with the string’s end. This results is the original input with a single letter deleted.

To illustrate how this works, I printed out the concatenation each time. You can see that the program continues until the result is a palindrome.

Although this works, reversing the string each time is costly. It reduces the algorithmic efficiency, making the solution “not scalable.” How can we decide if a string is a palindrome without reversing it?

Validating a palindrome using recursion

Judging a string to be a palindrome can be done using recursion. In programming, recursion is when a function calls itself.

Before we worry about removing any characters like we did above, we need a new function to verify a palindrome without reversing it:

function determinePalindromeRecursively($value){
    if ((strlen($value) < 2)){
        // echo "true \n";
        return true;
    }else{
        if (substr($value,0,1) == substr($value,(strlen($value) - 1),1)){
            echo substr($value,1,strlen($value) - 2) . "\n";
            return determinePalindromeRecursively(substr($value,1,strlen($value) -2));
        }else{
            // echo " Not a Palindrome"; 
            return false;
        }
    }
}

This method compares the first and last characters of the input. If they match, our code will remove them and pass the updated $value back around to itself, recursively. This continues until we get down to a single letter, or less – when we know that the original string was a palindrome.

To get the first character, we tell the substr() method to take the $value, start at the beginning (zero index), and collect a single element: substr($value,0,1)

To get the last character, we tell the substr() method to take the $value, start at the end (the string’s length minus one), and collect a single element: substr($value,(strlen($value) – 1),1)

To remove both the first and last letters, we tell substr() to start just past the first element (represented by an index of 1), and to collect the string’s length worth of characters minus two.

Notice that on each recursive loop, the string loses the front and back symbols.

Now, remember the original challenge: “Given a string, determine if you can make it a palindrome by removing at most 1 character.”

All that is left is to use our recursive function in tandem with removing a single character per loop.

function determinePalindromeRecursively($value){
    if ((strlen($value) < 2)){
        // echo "true \n";
        return true;
    }else{
        if (substr($value,0,1) == substr($value,(strlen($value) - 1),1)){
            echo substr($value,1,strlen($value) -2) . "\n";
            return determinePalindromeRecursively(substr($value,1,strlen($value) -2));
        }else{
            // echo " Not a Palindrome"; 
            return false;
        }
    }
}

function determinePalindromeRecursivelyWhileRemovingOneCharacter($value){

    for($i=0;$i<=strlen($value);$i++){
        $first_half = substr($value, 0, $i); // first half of string
        $second_half = substr($value, $i + 1);
        $string_with_one_char_removed = $first_half . $second_half;
        // echo "$string_with_one_char_removed \n";
         
        if(determinePalindromeRecursively($string_with_one_char_removed)){
            echo "true \n";
            return true;
        }
    }
    echo "false \n";
    return false;

}

determinePalindromeRecursivelyWhileRemovingOneCharacter("racecadr");

Give it a try, refactor my code, and see if you can solve this problem in a different way. There are other computer science puzzles about palindromes that you can apply this logic towards. Have fun!

November 13, 2021May 24, 2024

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:

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.