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

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!

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

In general, "divide and conquer" means to divide a problem into smaller (and often simpler) problems, solve each one separately, and then combine the solutions in some way.

In your specific example, you should divide the array into smaller arrays in some manner (e.g., divide it in half), find the smallest value in each smaller array, and then pick the smallest solution of these sub-problems as the solution to the overall problem. Each sub-problem can be solved using the same divide-and-conquer approach, with the limiting case being an array of sufficiently small size (e.g., 1 or 2) that you can solve the problem directly.

1. If the contents of an array are random, that means you have to search each element until you find the one you're looking for. The longer the array, the longer the search time. This is called a "linear search".

2. If the contents of an array are already in some kind of order, you can take advantage of this order to optimize your search (and reduce your search time). For example, names in a phone book are sorted alphabetically. You can open the phone book in the middle: if you name you're looking for is "lower than" the name in the middle, then continue searching in the left side of the book. If it's higher, then search the right half. This is called a "binary search", or "Divide and Conquer".

3. It's possible to quantify how efficient or inefficient a given search algorithm is. This is called "Asymptotic", or "Big O-Notation":

    
    Class                         Search algorithm
    -----                         ----------------
    Data structure                Array
    Worst case performance        O(log n)
    Best case performance         O(1)
    Average case performance      O(log n)
    Worst case space complexity   O(1)

U can go with the following algorithm.

getSmallest(int a[])
{
  int n=a.length;
  if(n==1)
    return a[0];
  else
   {
        x=remove first element from a;
        create another array b with a size smaller by 1 than array a
        if(x<getSmallest(b))
            return x;
        else
           return the smallest returned by the recursive call 
   }
}

http://ankzcode.blogspot.in/2012/11/find-minimum-without-linear-search.html

Code at the link implements the same.