[socksy]

Well I would posit that it would be hard to get to this code in a language with unbounded integers where (low n + high n) causes an OOM error, because in order to run this code, you first need an array n units wide.

You could argue that the array itself could take up most of the space leaving no room for the indices, but that's hardly a fault with the algorithm, as now you've got a computer that basically can't do anything due to overloading. Whereas overflowing a 32 bit integer is a much more likely occurrence that arguably the algorithm should account for.

[chowells]

Why does everyone talk about binary search in terms of arrays? Binary search works with any monotonic function. Looking up a value in a sorted array is just a special case of a monotonic function.

[LegionMammal978]

Because the 'bug' as presented in the article applies to binary search over an array that has a natural maximum length. If you weren't using an array, there'd be nothing constraining the magnitude of the indices, so you might as well go straight to bigints.

[chowells]

Of course there's a natural constraint: the type of the function. You can't pass a bigint to a function that expects an int. And if you are just blind casting, it turns out you have a similar bug: you are calling the function with different arguments than you think you are. It's the same underlying problem with a different expression in some cases.