JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: another tutorial on binary search (response to post by abstractwhiz) | Reply
So it does.

I guess this is another one of those things that really should have caused me to fail something a long time ago, but hasn't. Weird.
Re: another tutorial on binary search (response to post by antimatter) | Reply
apparently, making the lower and upper bound exclusive instead of inclusive makes it possible to just use (lo + hi) / 2 instead of lo + (hi - lo + 1) / 2.

This still causes trouble if hi and lo both go negative, since the rounding behaviour of integer division changes from round down to round up, messing things up. This doesn't happen if you're just searching an array, since an array index won't be negative - but it can happen if you're binary searching over a range that includes negative and positive numbers. The lo+(hi-lo)/2 makes sure this doesn't happen. I'm fairly certain lovro mentioned this in the article.
Re: another tutorial on binary search (response to post by Kawigi) | Reply
The plus one is right before the beginning of the "Real numbers" section. The last code snippet says that there is a nasty bug in it, and the following paragraph says "The solution is to change mid = lo + (hi-lo)/2 to mid = lo + (hi-lo+1)/2, i.e. so that it rounds up instead of down."

I'm still not sure that the linked algorithm fails when using a <= condition as opposed to a < condition. In fact, the code provided works using the former already. I agree that it is important to keep the distinction in mind when doing discrete binary search, but it seems to me that once you've committed a correct implementation to memory, it will always be right the first time, no matter the condition type or whatever.
Re: another tutorial on binary search (response to post by antimatter) | Reply
Right, and that's what I do in my spiel about binary searching, too, I'm just pointing out that potential for overflow is the only difference between (lo + hi) / 2 and (lo + (hi - lo) / 2). But I'm wondering where you got (lo + (hi - lo + 1) / 2).

The distinction of < vs. <= is only really significant if the problem is discrete (if it were continuous, one is a "good enough" estimation of the other). The distinction is whether your descrete space is "FFFFFFFTTTTTTTT" or "TTTTTTTTFFFFFFF" - basically if your function that you're using to figure out which side of the pivot is the right side includes the pivot when you take the top half or includes the pivot when you take the bottom half. The first case is a < case, because p tells you if the answer is < the answer or >= the answer. The second is a <= case, because p tells you whether the answer is <= the answer or > the answer. (Note - I'm profusely using symbols because I can't think of a way to write it that feels more clear to me).
Re: another tutorial on binary search (response to post by Kawigi) | Reply
Also, I don't see the +1 anywhere, but if you had a <= comparison rather than a < comparison, you'd need it.

I'm not sure what you mean by this, but since this problem is discrete, it should never be necessary to use <=, should it?

The basic concept of binary search is to pick the middle and see where it lies, and (lo + hi) / 2 is the most natural way to express that, even though it runs into problems with integers. Thus it makes more sense to me to alter the algorithm to accommodate this natural representation, rather than the other way around, and since this can be done just by changing the representation of the bounds from inclusive to exclusive, that's perfectly acceptable to me. More importantly, I think it's less to type, and I don't have to think about it, so I code faster :)
Re: another tutorial on binary search (response to post by antimatter) | Reply
Well, (lo+hi)/2 is the same as just lo+(hi-lo)/2 except that it's more likely to overflow. Also, I don't see the +1 anywhere, but if you had a <= comparison rather than a < comparison, you'd need it.

I'll add that I've written my own bit on binary searching on my blog - here and here. It was written in a similar flow to lovro's, but without all the nice pictures :-)
another tutorial on binary search | Reply
is here.

I found that the Java implementation there is even simpler, conceptually, then the one given in the feature article -- apparently, making the lower and upper bound exclusive instead of inclusive makes it possible to just use (lo + hi) / 2 instead of lo + (hi - lo + 1) / 2.

I found the linked article not long after having failed an SRM problem requiring discrete binary search (on a corner case, naturally), and I don't think I've ever gotten it wrong since.
RSS