In Divide and conquer strategy, three main steps are performed:
- Divide: Divides the problem into a small number of pieces
- Conquer: Solves each piece by applying divide and conquer to it recursively
- Combine: Combines/merges the pieces together into a global solution.
Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.
Given is an array of size $n$ and the task is to find a minimal element.
- Divide: The problem instance is characterized by the number of array entries $n$ and this step consists of moving to smaller problem instances $n' < n$, meaning smaller arrays. We only do this if $n > 1$. We have a couple of options at this point, like how many smaller arrays we want to have and how to derive them from the given array of size $n$. For simplicity we decide to derive two smaller arrays by splitting the array into two non-empty arrays. Here we have to choose the point where we want to split. E.g. at $\lfloor n/2\rfloor$, $\lceil n/2\rceil$ or at a random position within the array. We end up with two arrays: $a_1$ of size $n_1'$ and $a_2$ of size $n_2'$ with $1 \le n_i' < n$ and $n_1' + n_2' = n$.
- Conquer: If we are given an array of size $n=1$ we can claim that its element is minimal and return it.
- Combine: We have used recursion to determine the minimal elements $m_1$ of the array $a_1$ and $m_2$ of the array $a_2$. We compare the two elements, and return $m_1$ if $m_1 \le m_2$ otherwise we return $m_2$. Another option would be to return $m_1$ if $m_1 < m_2$ and otherwise return $m_2$.
Here's a Python (3) function that does the trick:
def find_min(arr): """ Return the least number in nonempty list `arr`. """ len_arr = len(arr) assert len_arr > 0 # Base case: if len_arr == 1: return arr # Divide... mid = len_arr // 2 # floor of len_arr/2; thus, mid ≥ 1 m1 = find_min(arr[0:mid]) m2 = find_min(arr[mid:len_arr]) # ... and conquer: return min(m1,m2)
(In Python, the default lower and upper bounds for "slices"
len(arr) respectively, so the third- and fourth-to-last lines could be written more concisely. But I can't assume all readers are fluent in Python.
Of course, this function is "unPythonic" for an even more glaring reason — the
min builtin does everything
find_min does, and more: it can accept a list as argument, and then it returns the least element in the list.)
Note that a recursive, divide-and-conquer approach to this problem performs slightly worse than a straightforward iterative approach, because of the function-call overhead. However, both are $O(n)$ in the size of the array: any algorithm has to examine every element of the array, and make the same number ($n-1$) of comparisons or calls to