Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Find Min with Recursion


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
33 replies to this topic

#21 frob   Moderators   -  Reputation: 22218

Like
0Likes
Like

Posted 30 January 2014 - 06:40 PM

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.


Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


Sponsor:

#22 Álvaro   Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 30 January 2014 - 07:56 PM

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.

#23 Álvaro   Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 30 January 2014 - 07:57 PM

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


What part are you having a hard time with?

#24 shadowstep00   Members   -  Reputation: 527

Like
0Likes
Like

Posted 31 January 2014 - 03: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.

 

6z1w5u.png


Edited by shadowstep00, 31 January 2014 - 03:58 AM.

Failure is not an option...


#25 shadowstep00   Members   -  Reputation: 527

Like
0Likes
Like

Posted 31 January 2014 - 04: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;
		}
	}
}

Edited by shadowstep00, 31 January 2014 - 04:54 AM.

Failure is not an option...


#26 rip-off   Moderators   -  Reputation: 8515

Like
2Likes
Like

Posted 31 January 2014 - 05: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.



#27 Álvaro   Crossbones+   -  Reputation: 13645

Like
1Likes
Like

Posted 31 January 2014 - 06:54 AM

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);
}


#28 rip-off   Moderators   -  Reputation: 8515

Like
1Likes
Like

Posted 31 January 2014 - 08:08 AM

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.



#29 shadowstep00   Members   -  Reputation: 527

Like
1Likes
Like

Posted 31 January 2014 - 08:10 AM

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...


#30 Álvaro   Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 31 January 2014 - 08:14 AM

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



#31 shadowstep00   Members   -  Reputation: 527

Like
0Likes
Like

Posted 31 January 2014 - 08:17 AM

Right laugh.png


Failure is not an option...


#32 Álvaro   Crossbones+   -  Reputation: 13645

Like
1Likes
Like

Posted 31 January 2014 - 08:20 AM

Yes, returning the index is a good solution:

unsigned recursive_min(double *data, unsigned n) {
  if (n <= 1) // [EDIT: Was `n == 1'. Thanks, rip-off.]
    return n - 1; // returns -1 for an empty input
  unsigned left_index = recursive_min(data, n/2);
  unsigned right_index = recursive_min(data + n/2, n - n/2) + n/2;
  return data[left_index] < data[right_index] ? left_index : right_index;
}

Edited by Álvaro, 31 January 2014 - 10:39 AM.


#33 rip-off   Moderators   -  Reputation: 8515

Like
1Likes
Like

Posted 31 January 2014 - 10:28 AM


// returns -1 for an empty input

It would, if the test were n <= 1.


Edited by rip-off, 31 January 2014 - 10:29 AM.


#34 Álvaro   Crossbones+   -  Reputation: 13645

Like
1Likes
Like

Posted 31 January 2014 - 10:39 AM


It would, if the test were n <= 1.

 

Ooops! Brain fart! :)






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS