# Binary Search question

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

## 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 on other sites
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 on other sites
I was referring to binary search on an array

##### 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 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 on other sites
Quote:
 Original post by GinkIn 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 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 on other sites
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.

1. 1
2. 2
Rutin
19
3. 3
khawk
19
4. 4
5. 5
A4L
11

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633771
• Total Posts
3013761
×