computer science – 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/

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!

December 21, 2021December 1, 2022

Array Rotation in PHP

An operation to rotate an array will shift each element to the left. We can perform this function X number of times depending on the input parameters. Since the lowest index element moves to the highest index upon rotation, this is called a circular array.

All we need to do is remove the first element of the array, save it in a variable, and then attach it to the end of the array. This can be done inside of a loop that iterates the number of times that we want to rotate the data. The function can take in the original array and the number of rotations. It returns the newly rotated array:

function rotateLeft($array, $rotations) {     
    for($i=0;$i<$rotations;$i++){
        $firstElement = array_shift($array);
        array_push($array, $firstElement);
    }
    return $array;
}

Although this code will work, and gets the job done, it is slow. When I tried this as a solution on HackRank (a code challenge website) it passed 9/10 test cases. It failed once, citing “time limit exceeded”.

The problem is with array_shift. It’s a PHP function that removes “the first value of an array off and returns it.” This shortens the array by a single element, moving everything else down one index. The algorithmic efficiency (expressed in Big-O notation) of array_shift() is O(n). That means, the larger the input array, the more time it will take to complete.

Next, I tried using array_reverse and array_pop. I figured that since array_pop() has a constant algorithmic efficiency, noted as O(1), it would help. Regardless of the size of the input, it would always take the same amount of time. But, due to the use of array_reverse (twice!) it was even slower:

function rotateLeft($array, $rotations) {
    for($i=0;$i<$rotations;$i++){
        $array = array_reverse($array);
        $firstElement = array_pop($array);
        $array = array_reverse($array);
        array_push($array, $firstElement);
    }
    return $array;
}

Finally, I found a solution that was performant:

function rotLeft($array, $rotations) {
        $remaining = array_slice($array, $rotations);
        array_splice($array, $rotations);
        return array_merge($remaining, $array);
}

This code does not need to use any kind of loop, which helps to speed things up. First, array_slice() grabs the elements up to the point that the data should be rotated, and saves them to the variable $remaining. Next, array_splice() removes those same elements. Lastly, array_merge() glues the elements back together in the expected, rotated order.

This sort of computer science programming challenge can commonly be found during software engineering job interviews. When coming up with an answer, it is important to consider speed and performance. Understanding computing cost-effectiveness and Big-O can be a deciding factor in how your coding skills are judged.