Hacker News Reader

Comment by tzs | Hacker News Reader

> int mid = low + ((high - low) / 2);

That may fix things in the case of searching a sorted array, but binary search can be used more generally than that. I think that fix might not work for some of the more general applications of binary search.

For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) < 0 and f(b) > 0, and you want to find an n in (a,b), if such n exists, such that f(n) = 0. Binary search on [a, b] is a reasonable approach.

If a < 0 and b > 0, then that mid computation could overflow on the subtraction.

View on HN

Bullet proof:

    mid = lo / 2 + hi / 2;

Well, that is, if your algorithm can tolerate a mid == 6, for hi == 7 and lo == 7. :) :) :)

Cough, cough; seriously though: here is a variant based on the above idea which takes care of the remainders, avoiding that problem:

   ;; TXR Lisp
   (defun mid (lo hi)
     (tree-bind ((lq lr) . (hq hr)) (cons (trunc-rem lo 2) (trunc-rem hi 2))
       (+ lq hq (trunc (+ lr hr) 2))))

trunc-rem has toward-zero truncation, with a remainder that is harmonized to that.

Based on my testing in the REPL, this is behaving sensibly.

Adding the quotients, and then adding to them the sum of the remainders, truncated by two, seems to be doing the trick.

(mid 7 7) is 7, (mid -7 -7) is -7 and various other cases are all sensible. (mid k (+ 2 k)) is yielding (+ 1 k), for both values being negative, either being zero, and zero-crossing cases. (mid k k) seems to be k for all k.

I think as of ISO C99, the / and % operators truncate toward zero. Unless I'm gravely mistaken, this is then nicely expressible in C as:

  lo / 2 + hi / 2 + ((lo % 2) + (hi % 2)) / 2;

It's mathematically well founded: we have added the truncations, and then continue working with the remainders. This is because the following expression in fact expresses the exact result.

  trunc(lo,2) + trunc(hi,2) + (rem(lo, 2) + rem(hi, 2))/2

where / is exact rational division! Dividing the remainders by two just continues the inexact division, completing it to exactness. What we're doing differently in the machine calculation is using truncating division on the sum of the remainders, which we need because mid is to be an integer result.

In that case, then you can to go back to

    int mid = (low + high) / 2;

but you'd have to constrain low and high to be in the range [-2^30, 2^30 - 1] so as to not overflow a (assuming 32-bit) signed integer. (And you're probably using 64-bit floating point, or similar, which has other fiddly bits.)

However, the article specifically talks about merge sort in arrays, so low (your "a") is always >= 0. The discovery was "oh, we went decades before someone had to sort an array with more than 2^31 elements". Frankly, it's akin to when we ran out of IPv4 addresses -- when it was originally built, there was some range over which the computation was defined to be correct, and we later discovered that we wanted to do computation outside that range.

I'm tempted to suggest

    (low / 2) + (high / 2)

but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop worrying about overflow altogether.

That won't get you the middle, these are integer divisions.

Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)

Plus, an extra operation, at least compared to some of the shift-based fixes.

Rouding error can be taken care of:

https://news.ycombinator.com/item?id=14908117

Reply on news.ycombinator.com