• Create Account

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.

33 replies to this topic

#21frob  Moderators

41248
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 occasionally write about assorted stuff.

#22Álvaro  Members

20254
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  Members

20254
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?

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

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

Failure is not an option...

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

#26rip-off  Moderators

10730
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  Members

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


#28rip-off  Moderators

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

738
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  Members

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

738
Like
0Likes
Like

Posted 31 January 2014 - 08:17 AM

Right

Failure is not an option...

#32Álvaro  Members

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

#33rip-off  Moderators

10730
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  Members

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