Beginner Problem Solving Patterns Part 2

Last time I wrote about the “ frequency counter” problem-solving pattern, I will introduce the “divide and conquer” problem-solving pattern this time. This problem-solving pattern is more advanced. I am here only to talk about the general idea of divide and conquer problem-solving pattern.

Divide and Conquer

Imagine a massive amount of data in an array; we want to search value within the left to the right. So the idea of divide and conquer is we start by dividing into smaller pieces and then doing something to each smaller piece to determine where to go next. It involves dividing a data set into smaller chunks and then repeating a process with a subset of data. Some of the well-known examples of divide and conquer problem pattern solving are binary search, binary search tree, quick and merge sort. Let see an example :

check out the problem here: https://leetcode.com/problems/binary-search/

One most straightforward way to solve the problem is with one single for loop and find if the target exists, then return its index; otherwise, return -1 (linear search). However, the time complexity will be O(n), which is not as efficient as utilizing divide and conquer a binary search method. Binary search gives time Complexity (O log N), which is so much faster than O(n). The example data above is little. Assume the data set in an array has millions. With linear time, it will take forever. The binary search method would be more optimal and efficient compared to a linear search. This problem is a classic example of a divide and conquers problem-solving patterns. In fact, The binary search method is utilizing divide and conquer the problem-solving technique to search for a solution.

How it works

Utilizing a binary search method to solve the problem

Above question, first of all, the binary search has to be sorted. The way that binary search works are getting the middle index and comparing it with the target number. If the middle index number is equal to the target number, then return its middle index. If the middle index number is less than the target number, we continue to search on the right by moving the start = mid +1. On the other hand, if the middle index is greater than the target number, we continue to search on the left side by moving the end =mid-1.

In summary, the idea of divide and conquer keeps searching the middle index until we find the target value we are searching for. Check if the middle index number is greater or lesser; from there, we can decide if we want to move the start index to the right or left of the middle index. That is it for now! Thanks for reading until the next one!