Comments by "Anony Mousse" (@anon_y_mousse) on "Bug in Binary Search - Computerphile" video.

I guess I didn't notice you writing it that way in the first video, but I've known about this weird way of getting half the distance between two indices for a long time and specifically avoided it because of this known issue. I generally use C and adding a single extra instruction that takes one clock is not a big deal for a compiled language. Even at a billion entries it's more than fast enough to not warrant worrying about it. This is one of those edge cases that can ruin your year and is probably one of the reasons that Knuth came up with that stupid phrase. I guess I should've paid more attention in that first video and chided you for it, but I was fighting my Python installation that didn't want to use numpy. Bad Mike!
5
@simpletongeek Maybe, just account for the possible off by one error depending on whether you're at an even or odd distance.
4
One extra clock per iteration is not too heavy a price to pay, especially considering that it'll only be executed log(N) times.
4
@jmodified I think everyone acknowledges that it's faster. The issue is that it'll yield incorrect results at large values of l and r. It's not exactly onerous to use the correct form of l += ( r - l ) / 2; It's a single extra clock cycle for compiled languages.
2
@minilathemayhem No, it's just going to yield an incorrect answer because of integer division, and every compiler I've tested optimizes division by two as a bitshift right by one, even at -O0.
1
@SimonVaIe The issue isn't whether to do a signed or unsigned shift right, but in the adding of two numbers when the allocation is near the boundary of available memory. When the addition of l and r causes an overflow, ( l + r ) / 2 will yield an incorrect value. One suggested solution is to use a larger integer type, such as 64-bit integers, but it's still recommended that you write your code in a type agnostic and portable way. Since the calculation in question will only run log(N) times, just quit trying to optimize yourself into a failure state and do it correctly from the start. And in case you weren't aware, every single compiler I've tested this on, will optimize n / 2 into n >> 1, or in Java parlance, n >>> 1, even at an optimization level of -O0. Check with Compiler Explorer if you don't believe it.
1
@SimonVaIe I don't think you're understanding what the actual problem is.
1