1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i solve my problem with your guideline ... thnx mvw..... $\endgroup$ – hydr Dec 8 '15 at 10:50
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.