Algorithm Action: Divide & Conquer

Photo by Anthony Intraversato on Unsplash

Algos, algos, algos: the cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a set of articles titled Algorithm Action.

Today, we’re checking out a specific problem solving pattern known as divide and conquer.

Take Command Of Divide & Conquer

The Divide & Conquer approach is important because, for a lot of problems, it usually greatly decreases time complexity. It involves dividing a data set into smaller chunks, applying some sort of condition to both, and then repeating the process with whichever subset of data passes, and on and on. The result is an approach that’s not only faster (Log(N)) but also easy to conceptualize.

Let’s take a look at a classic example of a problem that can be solved with this approach:

Given a sorted array of integers, write a function called search that accepts a value and returns the index where the value passed to the function is located. If the value is not found, return -1.

We’ll start with this dataset: ([1, 2, 3, 4, 5, 6], 11).

Here’s the function. Let’s run the above dataset through this function and see how it works:

function search(arr, val) {
    let min = 0; 
    let max = arr.length - 1;
    while (min <= max) {
        let middle = Math.floor((min + max) / 2); 
        let currentElement = arr[middle];
        if (arr[middle] < val) {
            min = middle + 1;
        } else if (arr[middle] > val) { 
            max = middle - 1;
        } else { 
            return middle; 
        }
    }
    return -1; 
}

Let’s go over this bit by bit here:

let min = 0; 
let max = arr.length - 1;

The variables min and max represent the smallest and largest indices for the array that is passed in.

while (min <= max) {
        let middle = Math.floor((min + max) / 2); 
        let currentElement = arr[middle];
        if (currentElement < val) {
            min = middle + 1;
        } else if (currentElement > val) { 
            max = middle - 1;
        } else { 
            return middle; 
        }
    }

The heart of this approach is the while loop we see above. In it, we start by initializing a variable, middle, which represents the index that’s more or less the middle of the array. That’s used in the variable currentElement for more legibility. Then we have an if/else statement. It’s responsibility is to change the min or max variables depending on the comparisons being made.

For instance, with the parameters ([1, 2, 3, 4, 5, 6], 11), the middle of the array is 3. We then ask if 11 is greater than 3. That’s a yes, so we set min to middle (which is 3) plus 1. The new middle is 4 and the cycle continues until the function returns -1.

It seems simple enough but I know I need far more practice with this for sure. Keep in mind that the Divide and Conquer approach is usually found as something to be used in a far more complex problem than what was used as an example in this article. We have to start somewhere though, don‘t we? :)

What do you think? If you liked what you read, consider connecting or dropping me a line at nick.echev@gmail.com!