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.
Got a tip for us?
Let us know
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
macOS Finding min and max using binary recursion.
- Thread starter 103734
- Start date
- Sort by reaction score
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.
Thats all I neededRecursion stops . . .
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.
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.
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
A compiler capable of parallelizing a recursive algorithm would likely be able to parallelize a simple loop as well. So... same deal.
I suspect that was the real reason but nobody had mentioned it.
