Jump to content
  • Advertisement
Sign in to follow this  
Gink

Binary Search question

This topic is 4698 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
Your terminology (what is middle?) is opaque.

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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!