Divide and conquer algorithm for finding the smallest value in the array

Question

an array a[1..n] of elements of some ordered type (i.e. x < y is always defined) and i want to find the smallest value in the array using a "divide and conquer" algorithm.

What does the assignment really mean?

Solution 1

Divide-and-conquer is an algorithmic technique that solves a problem by splitting the problem into smaller pieces, solving the problem in each piece, and combining the results together to form an overall answer. When the problem becomes sufficiently simple, it can be solved directly.

In this case, think about what would happen if you split the array in half. If you knew the minimum value in each half, could you figure out the minimum value overall? And when there's just one element left in the array, what's the minimum value in the array? If you answer this question, you can directly come up with a recursive divide-and-conquer algorithm for the problem.

Hope this helps!

Solution 2

The divide-and-conquer strategy solves a problem by:

1. Breaking it into subproblems that are themselves smaller instances of the same type of problem

2. Recursively solving these subproblems

3. Appropriately combining their answers

A good example is merge-sort!

http://en.wikipedia.org/wiki/Merge_sort

Comments

[user1253637]

i know the meaning of divide and conquer... but what does the line an array a[1..n] of elements of some ordered type (i.e. x < y is always defined) mean? Does it mean an unsorted array?

[templatetypedef]

@user1253637- Ah, sorry! I misinterpreted your question. Yes, it means that it's an unsorted array of elements. You don't know what those elements are (strings, integers, widgets, etc.), but any two elements are comparable, so it makes sense to find the minimum. You might want to clarify your question, since it seems like everyone is misinterpreting what you're asking. :-)

[Nicholas]

It means unsorted list, but operations like x<y is defined, so you'll be able to compare two elements.

[Ted Hopp]

Suggesting merge sort for this problem is weird. Finding the smallest element is an O(n) linear scan; merge sort is O(n log n).

[Kevin]

@TedHopp yeah but merge sort does divide and conqure