PDA

View Full Version : Finding min and max using binary recursion.

103734
Nov 26, 2010, 10:45 PM
I need to find the min and max number in a integer array using binary recursion. I'm familiar with binary search, and recursion, but not binary recursion. I'm not sure if its just been a long day and i'm brain dead or what but I'm drawing a blank here; just need a very simple break down of what this means to jump start my brain. When I mean simple, I really mean it, don't need anything in depth.

chown33
Nov 27, 2010, 01:05 AM
Split array into two halves. Call self with lower half. Call self with upper half. Return min or max of two halves. Recursion stops when a half-array is a single element.

103734
Nov 27, 2010, 01:50 AM
Thanks!:D Thats all I needed

PatrickCocoa
Nov 27, 2010, 02:59 AM
Recursion stops when a half-array is a single element.

Just to clarify, the above sentence means that your first action should be to test the length of the array. If it's one, then you're done. If not, go ahead and do the splitting thing.

vocaro
Nov 27, 2010, 09:34 PM
Split array into two halves. Call self with lower half. Call self with upper half. Return min or max of two halves. Recursion stops when a half-array is a single element.

Unless this is strictly an academic exercise, that seems like a silly way to search for min/max. Why not a simple linear search? The time complexity would be the same, and the constant factor would be smaller as well. Simpler to code and to read too.

lee1210
Nov 27, 2010, 10:18 PM
Unless this is strictly an academic exercise, that seems like a silly way to search for min/max. Why not a simple linear search? The time complexity would be the same, and the constant factor would be smaller as well. Simpler to code and to read too.

Maybe there's a billion elements and you are writing in a language or with a compiler that can parallelize this for you?

But really, because that's what the homework said to do.

-Lee

vocaro
Nov 27, 2010, 10:37 PM
Maybe there's a billion elements and you are writing in a language or with a compiler that can parallelize this for you?

A compiler capable of parallelizing a recursive algorithm would likely be able to parallelize a simple loop as well. So... same deal.

But really, because that's what the homework said to do.

I suspect that was the real reason but nobody had mentioned it.

chrono1081
Nov 28, 2010, 04:27 AM
But really, because that's what the homework said to do.

-Lee

I loled at this!

103734
Nov 28, 2010, 05:47 PM
But really, because that's what the homework said to do.

-Lee

correct!

wrote the code last night, works perfectly. Thanks.