Divide & Conquer and Binary Search
Divide and conquer is an approach in some common programming problems. One such case is finding the longest common prefix which involves developing a solution to find the longest common prefix string in an array of strings.
["international", "interstellar", "interruption"]inter
However, we will not dive into solving this problem in this article. We will explore an approach to solving this problem; divide and conquer and use an algorithm; binary search to illustrate how it works.
The Approach
Divide and Conquer is a technique of breaking a problem into simpler problems that are easier to solve and combining the solutions to solve the original problem.
Let’s take a problem such as arranging two decks of cards. After playing a game of cat and mouse with a friend, it’s time to split your two decks of cards. In order to arrange the cards at a fast rate, you split the pile of cards with your friend and both of you sort out the mess. The original problem in this case, is arranging the pile of cards and the simpler problems are arranging smaller piles of cards between the players.
Divide and conquer is usually described as involving steps.
Divide step, breaking a problem into simpler problems.
Conquer step, solving the simpler problems usually referred to as sub problems. In this step we repeat a process of solving the problem until a condition is met, this condition is referred to as the base case.
Combine step, involving putting the solved sub problems together.
One variation, of this approach is Decrease and Conquer. In this variant, the original problem is broke up into one simpler problem.
Let’s say you have your deck arranged at this point in the article and you want to show your friend your favorite card. Holding the deck of cards, you could start from the first card on top in whichever direction, looking for your favorite card. This would work, but it would be quite inefficient if you have to go through all cards. This is linear search. How would you do it better?
If your favorite card is seven spades. You could split the deck in half, check to see your current position. If the cards on one side are less than seven you would continue searching on the other split deck. Repeating this process would eventually lead you to find your card in fewer steps. That’s if your card isn’t mixed up in the previous deck or lost! This is binary search.
The Algorithm
Binary search is an algorithm that searches in a sorted collection for a target. It works by comparing the target to the middle element in a collection. If the target is greater than the middle element, the left elements are discarded. If the target is less than the middle element the right elements are discarded. This process is repeated until the middle element is equal to the target and if no further splitting can be done. The target does not exist in the list.
This process of repeating the same algorithm in sub problems is commonly referred to as recursion.
Assuming we have a collection of elements, from a popular sequence. The target is 21. We would split the collection as shown below.
+---------------------------------+--------------+---------+
| Collection | Middle Index | Element |
+---------------------------------+--------------+---------+
| 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 | 4 | 3 |
+---------------------------------+--------------+---------+
| 5, 8,13,21,34 | 2 | 13 |
+---------------------------------+--------------+---------+
| 21,34 | 1 | 21 |
+---------------------------------+--------------+---------+You will notice when we split an odd number, we round it down. To eliminate elements on a side we change the position of our indexes. Think of it this way, if our target will be in our less than section, the end index should be one position in front of the middle position. In-front because we want to ignore all elements behind our current position and one position more we already know the middle position is not equal to the target. The same logic applies when the target is in greater than split, we bring the start index one position in-front of the middle position.
The Code
Binary search can be done implemented in an iterative approach or a recursive approach.
The Prestige
Divide and conquer is an approach of breaking down a problem into sub problems and combining the solutions. In binary search, on a sorted array of numbers, we divide (decrease) the array of numbers(search space), conquer the sub problems by recursively looking at the middle point for our target and splitting until we find our target the base case condition.
Note binary search works on a sorted collection of elements. This means it’s performance is good when the lost is sorted and terrible otherwise. Let’s wrap up with some complexity analysis.
In our example on retrieving our favorite card from a deck of card, we reduce the number of cards we have to search through each time we split the deck. In a standard deck of 52 cards, on our first split we reduce the deck to 26 cards. On our second split we reduce the cards to 13 cards and proceeding to the next splits until we find our intended card. It would take at most six(6) splits to find our card.
If we use our original to two decks situation, we have 104 cards initially assuming the cards are sorted as one deck. We would have one more step to get our cards to 52 and proceed, at most seven(7)splits. Each time we double our cards(search space) we add one more split. Pretty sweet.
The Icing
This patterns and situations can be represented mathematically. For a collection of elements n , we need m number of splits to get our target. Thus a double in our collection 2n results in m+1 splits.
A mathematically function that represents such change is logarithms, if you need some more explanation on this, I recommend this video.
To see it clearly, if you have a collection of elements which are to the power of two that is 1,2,4,8,16.The result of using the logarithm function to base two(2) is equal to m. Thus m+1 is the maximum number of splits we would require to find our target. Ready for the cherry.
+----+--------------+
| n | log base 2 n |
+----+--------------+
| 1 | 0 |
+----+--------------+
| 2 | 1 |
+----+--------------+
| 4 | 2 |
+----+--------------+
| 8 | 3 |
+----+--------------+
| 16 | 4 |
+----+--------------+The cherry
To calculate the time complexity of binary search we can apply our knowledge seen in this case. Therefore in the worst case binary search worst time complexity is O(log n).
Enjoy!
Level Up Coding
Thanks for being a part of our community! Subscribe to our YouTube channel or join the Skilled.dev coding interview course.
