Find Min with Recursion

shadowstep00 · 2014-01-31T16:39:02

So I am trying to create an algorithm in C that finds the Min number of an array A[n] using recursion. What the algorithm does is split the array to 2 equal subsections until the subsections become with only one position left. Until n = 1 so min = A[0]. Then it goes back and the subsectopms start comparing each other. This is where I have gotten so far. #include <stdio.h> #define N 10 int min_num(double T[],int n); int main() { double T[]={4,5,10,5,7,3,6,2,8,9}; double min; min = min_num(T,N); printf("min = %g\n",min); return 0; } int min_num(double T[],int n) { double min; // the min number if (n == 1) min = T[0]; else { int k; k = n/2; double SubsectionA_T[k]; double SubsectionB_T[n-k]; int i; double x,y; for (i=0;i<k;i++) SubsectionA_T[i] = T[i]; for (i=k; i<N; i++) SubsectionB_T[i] = T[i]; x = min_num(SubsectionA_T, k); y = min_num(SubsectionB_T, n-k); min = x; if (x > y) min = y; } return min; }

For Beginners

Started by shadowstep00 January 30, 2014 03:41 PM

32 comments, last by alvaro 10 years, 2 months ago

frob

46,221

January 31, 2014 12:40 AM

I frob missed the trick:

You can process the elements two at a time, compare them and then only use the smaller of the two to try to update the minimum and only use the larger of the two to try to update the maximum. This requires about N*3/2 comparisons.

I am not making any claims about practical usability of this trick: It's just a neat little puzzle.

Meh, it is a micro-optimization in the part that doesn't dominate. My hunch is that the added branch would slow things down if you were worried about performance.

As mentioned, there are solutions that require zero comparisons. Keep the collection sorted in the first place and don't worry about it.

alvaro

21,604

January 31, 2014 01:56 AM

No, it's not a micro-optimization: It's the solution to a brain teaser. I think I posed the question correctly. If you don't enjoy that kind of thing, that's OK. But trying to argue about the real-life complexities of the situation is missing the interesting mathematical curiosity that I was pointing at.

alvaro

21,604

January 31, 2014 01:57 AM

So guys any ideas on how to make the code return except for the value also the position of min?

What part are you having a hard time with?

shadowstep00

738

Author

January 31, 2014 09:57 AM

The problem is that the index keeps changing during the recursions.

And I dont want to make a classical search in order to find where the min is located inside the A[10].

I wanna know if there is a solution on how to return the index without searching.

Failure is not an option...

shadowstep00

738

Author

January 31, 2014 10:53 AM

The easy way is with just searching. Is there another more clever way?


#include <stdio.h>

double recursive_min(double T[], int n,int *index);

int main(){
	double T[10] = {4,50,-10,-6,7,-11.6,7,-1,8,-9};
	double min;
	int index;
	min = recursive_min(T,11,&index);
  
    printf("min = %g\n", min);
    printf("Index = %d\n",index);
	
}

double recursive_min(double T[], int n,int *index){
	int i;
	if (n == 1)	
		return T[0];
	else{
		double x = recursive_min(T,n/2,index);
		double y = recursive_min(T + n/2, n - n/2,index);
		if (x < y)
		{
			for (i = 0; i<=n/2; i++){
				if (T[i] == x) 
					*index = i;
		}
			return x;
		}
		else 
		{
			for (i =n/2 ; i<=n; i++){
				if (T[i] == y) 
					*index = i;
				}
			return y;
		}
	}
}

Failure is not an option...

rip-off

11,000

January 31, 2014 11:03 AM

I wouldn't like that solution as it scans the data many times. You might as well just have an iterative solution at that point. Also, there is a bug, if the function is passed a one element array, the index is not set.

A nicer solution might be to change the signature to accept a range:

double recursive_min(double *array, int start, int end, int *index);

Here, end is "one past the end", i.e. for an array of size N, end would be N.

So now, in the recursion, pass the same array (no pointer arithmetic), but modify the start / end parameters appropriately. Thus, you would then always know the absolute index even as you go deeper in the recursion.

blog | twitter

alvaro

21,604

January 31, 2014 12:54 PM

rip-off's suggestion is good.

Alternatively, you can keep the original signature, if you are a little bit careful:

double recursive_min(double *data, unsigned n, unsigned *index) {
  if (n==1) {
    *index = 0;
    return data[0];
  }

  unsigned index_left, index_right;
  double left = recursive_min(data, n/2, &index_left);
  double right = recursive_min(data + n/2, n - n/2, &index_right);

  return left < right ? (*index = index_left, left) : (*index = index_right + n/2, right);
}

rip-off

11,000

January 31, 2014 02:08 PM

Note that returning the index instead of the value can be a good solution. You can handle an empty array by returning an invalid index, such as -1 or N, but client code can still quickly get the value by using the index. For more general searching algorithms, this can handle the case where no matching element is found, too.

blog | twitter

shadowstep00

738

Author

January 31, 2014 02:10 PM

thanks :)

Is it necessary to have 2 different index?

Because I think this also works too.


double recursive_min(double T[], int n, int *index){
	if (n == 1){
		*index = 0;
		return T[0];}
	else{
		double x = recursive_min(T, n/2, index);
		double y = recursive_min(T + n/2, n - n/2, index);
		if (x < y){
			return x;}
		else {
			*index = *index + n/2;
			return y;}
	}
}

Failure is not an option...

alvaro

21,604

January 31, 2014 02:14 PM

If the minimum is in the first half, the index will be lost when you search the second half.