Divide and Conquer: A Big O Pattern

As stated in my last post, I have been discussing Big O and how we can refactor our code to make it the most efficient it can be. To take a look at that post, click here.

Anyways, one common pattern we can use when trying to solve a Big O problem is to Divide and Conquer (DnC). What is DnC? When you divide and conquer, you are dividing a data set into smaller chunks, and then repeating a process with a subset of data. This type of pattern can greatly decrease the time complexity.

Imagine if you we given the following challenge:

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

One way to solve this issue is by writing the following code:

This isn’t horrible, but the time complexity is O(n). However we are able to make that much quicker by doing the following:

Rather than the original linear search we can complete the task with a binary search. With this code, we are checking the middle of the array to see if it is greater or less than the given value. Then, if it isn’t equal, it moves to either the left or right depending on whether it is greater or less than. With this code, the time complexity is Log(n) and much quicker than the original.

Linear search goes through the entire array to try and find the answer. However, because we are working with a sorted array, we can divide it in half to try and find our answer. Once we divide the array, we then see if the value we are searching for is greater than or less than the middle.

This is just one example to how we can make our code quicker!