Monday, November 5, 2012

Find the minimum without linear search / WAP to find the minimum value in an array using divide and conquer approach

Problem Statement

Find the minimum value in an array without linear search/
WAP to find the minimum value in an array using divide and conquer approach

Solution:

Approach is using divide and conquer.

Divide the array in smaller sub-sets of two.
Find the minimum of each sub-sets.

Finally compare and return the smallest/minimum value of the two largest sub-sets.

Code:

<ankzcode>
 #include <stdio.h>

int findMin(int a[], int l,int h)
{
    int pivot = (l + h) / 2;
    int minl=-1, minh = -1;

    if ( (pivot - l ) > 1) {
        minl = findMin(a, l, pivot);
    }
    else {
        minl = (a[l] > a[pivot])?a[pivot]:a[l];
    }
    if ( (h - pivot ) > 1) {
        minh = findMin(a, pivot, h);
    }
    else {
        minh = (a[l] > a[pivot])?a[pivot]:a[l];
    }

    return (minl>minh)?minh:minl;
}

int main()
{
    int a[]={5,2,9,10,3};
    printf("%d\n",findMin(a, 0, 5));
    return 0;
}

</ankzcode>

2 comments:

  1. can u post one to find min?
    edit the same algo if u can or a
    single algo to find both will be much appreciates :)

    ReplyDelete
  2. This post was to find min iguess .. ;-)

    To find max u can use following function:

    int findMax(int a[], int l,int h)
    {
    int pivot = (l + h) / 2;
    int maxl=-1, maxh = -1;

    if ( (pivot - l ) > 1) {
    maxl = findMax(a, l, pivot);
    }
    else {
    maxl = (a[l] < a[pivot])?a[pivot]:a[l];
    }
    if ( (h - pivot ) > 1) {
    maxh = findMax(a, pivot, h);
    }
    else {
    maxh = (a[l] < a[pivot])?a[pivot]:a[l];
    }

    return (maxl<maxh)?maxh:maxl;
    }

    ReplyDelete