Binary Search question
Author
In a binary search, is there a difference between assigning the high value to the middle and the high to middle-1? Seems random but just making sure..
Your terminology (what is middle?) is opaque.
There are three visitation schemes for binary search. They are pre-order, in-order and post-order.
You can also have depth-first and breadth-first search strategies. You'll have to translate all that to your internal model to make it useful to you.
Happy hacking!
There are three visitation schemes for binary search. They are pre-order, in-order and post-order.
- Pre-order: Visit the parent node data before the children.
- In-order: Visit the left sub-tree, then the parent, then the right sub-tree.
- Post-order: Visit the left and right sub-trees before visiting the parent node data.
You can also have depth-first and breadth-first search strategies. You'll have to translate all that to your internal model to make it useful to you.
Happy hacking!
A common way to do a binary search on an array is to pass in the lower and upper bounds, check the middle element, reset the bounds, and repeat.
Anyway, reset the bounds in whatever way makes the most sense to you. Make sure you test all the corner cases to verify you're not either missing an element or going into an endless loop.
Anyway, reset the bounds in whatever way makes the most sense to you. Make sure you test all the corner cases to verify you're not either missing an element or going into an endless loop.
binary search
low
something
high
if array[something] > searched element high = something - 1 (because array[something] is bigger)
That is, if high is part of possible target space. So if you belive high could have the searched value, or you'd like to be at safe side and your implementation would terminate for sure, you could set high = something.
Actually effectivity depends on implementation so both versions could be right.
BTW have you tried to return the lowest valid element?
low
something
high
if array[something] > searched element high = something - 1 (because array[something] is bigger)
That is, if high is part of possible target space. So if you belive high could have the searched value, or you'd like to be at safe side and your implementation would terminate for sure, you could set high = something.
Actually effectivity depends on implementation so both versions could be right.
BTW have you tried to return the lowest valid element?
Quote:Original post by Gink
In a binary search, is there a difference between assigning the high value to the middle and the high to middle-1? Seems random but just making sure..
It will work perfectly either way. The only difference is the redundancy in doing so - you already know middle isn't the value you're looking for, so why include it in the resulting subset of elements ?
Author
True storm.. I found that in the end it evens out tho. I was just wondering if there were certain indexes or something that the mid version could find faster, but I couldnt find any pattern so I'm assuming it's just random.
It depends on the details of the algorithm you're talking about. Depending on how exactly the algorithm is written, one way could be correct, or the other way could be correct, or both ways could work with one being slightly better on average. High and middle don't mean anything if we don't know what they refer to or how they are being used.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
