Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.

Question

In Divide and conquer strategy, three main steps are performed:

1. Divide: Divides the problem into a small number of pieces
2. Conquer: Solves each piece by applying divide and conquer to it recursively
3. 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.

Answer 1

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[0]
    # 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" low:high of arr are 0 and 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 min.

Answer 2

Given is an array of size $n$ and the task is to find a minimal element.

1. 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$.
2. Conquer: If we are given an array of size $n=1$ we can claim that its element is minimal and return it.
3. 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$.