Dividing and conquering coding algorithms

The easiest way to solve a problem isn’t always the best one

In this blog post, I will try to demonstrate the value of the ‘divide and conquer’ approach to solving algorithms efficiently. At its core, dividing and conquering means splitting large problems into smaller sub-problems (which can themselves be divided) until the sub-problems are small enough to solve. By solving its sub-problems, you will eventually solve the large problem. This approach is neither new nor used solely for coding challenges, but is an efficient way to go about solving problems you may face in your workplace or the dreaded coding interview. As an example, I will write two solutions for a simple search algorithm, one both dividing and conquering, and the other woefully straightforward. Let’s start with the easy one, shall we?

Suppose we have a sorted array of numbers and we need to search it to see if it contains a specific number, let’s say 12. The simplest way to solve this algorithm would be to iterate through the whole array, compare every value to the given number, and return true once we’ve found our number. In javascript, that may look something like this:

function search(arr, num) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === num) {
      return true
    }
  }
}
let arr = [1,2,3,4,5,6,12,14,15,18]
search(arr, 12) // => true

This method will work well for short arrays like the example above, but as a clever reader, you’ve probably already spotted the problem with this method. What if our array contains millions of numbers? In the worst-case scenario, this method would have to iterate through the entire array in order to find the number. This method is not very efficient. Algo experts would say that it has ‘linear time complexity,’ which is to say that the length of time to find a solution scales linearly with the size of the dataset. If the dataset is small, the average solution will be quick; if the dataset is humongous, the average solution will take a long time to find. Luckily, there’s a better way.

link from: https://brainberries.co/funny/there-has-to-be-a-better-way-24-gifs/

Enter the divide and conquer method. Using this technique, let’s try to break down the large problem into smaller problems and see if we can improve our solution’s time complexity.

One of the hardest things about this approach is that it requires a different way of thinking about the problem. One has to dismantle the problem and rebuild it. I found this description from another blog post illuminating:

“Let’s say I handed you a dictionary and asked you to look up the definition for search. Then I asked you to the definition for binary. Would you start at about the same page for both?

I reckon for search you’d start somewhere a bit after the middle, and for binary, you’d start somewhere near the beginning. I reckon that because your efficient human brain learned early on that dictionaries are in alphabetical order, and to look for a word starting with “s” near the beginning was a waste of time.”

In other words, we already know another way to approach this problem, we just have to frame it correctly. Put in the above terms, our first solution is like searching through every word in the dictionary in order so that we can find one word. But that’s not how you or I would search a dictionary. We can use certain known characteristics of the word (such as its beginning letter) to narrow down our search to a reasonable size. Now the task is to frame this logic in a programmatic way.

At this point, when we divide and conquer the problem, two smaller problems reveal themselves. When I look in the dictionary for a word like ‘salt’, I would probably start after the halfway point, open to a random page, and compare words to see how close I was. If I see the word ‘trout’, then I know I went too far, and so on. So our problems are: how can we find the midpoint of the array, and how can we refactor our search using that information? In this problem, the answer turns out to be recursion.

First, let’s create our function and find our midpoint. That can be done like so:

function binarySearch(num, arr) {
  let middle = Math.floor(arr.length / 2)
}

The Math class in javascript will help us find our midpoint without needing decimals (it’ll round down). Next, we need to write an escape clause for our recursion. That could look like:

if (arr.length === 1 && arr[0] != num) {
  return false;
}

This way, if we iterate through the whole array without finding anything, the recursion will eventually stop. Now we need our comparison to find our number, like:

if (num === arr[middle]) {
  return true
}

Now, if our code finds a match, it can stop. Finally, the only code left to write is the recursive part, which will check compare the midpoint in the array to our number. If the number is higher than our midpoint, we can slice out the lower half of the array since we know, and if the number is lower than our midpoint, we can get rid of everything after the midpoint. In essence, this logic will halve our array every loop until it finds our number. Here’s what it may look like:

if (num === arr[middle]) {
    return true
} else if (num > arr[middle]) {
    binarySearch(num, arr.slice(mid))
} else if (num < arr[middle]) {
    binarySearch(num, arr.slice(0, mid))
}

Finally, here is the code in total:

This binary search function will not be much faster than a simple iteration when dealing with small datasets, but it will be able to search through massive datasets much more efficiently. Rather than searching every index of the array, it will be able to effectively remove huge chunks of data simply using logic. I hope that this is a helpful guide for you, and if nothing else, you now know how to write an efficient searching algorithm!