The (lo + hi) / 2 bug on a sorted sequence of 2,000,000,000 elements (no array: see Overflow.Sequence)
====================================================================================================

Plain int arithmetic, lo=1000000000 hi=1999999999:
  lo + hi            = -1294967297
  (lo + hi) / 2      = -647483648
  lo + (hi - lo) / 2 = 1499999999
  (lo + hi) >>> 1    = 1499999999

Broken (lo + hi) / 2, searching for the last element, 1999999999:
  lo=0 hi=1999999999 lo+hi=1999999999 mid=999999999
  lo=1000000000 hi=1999999999 lo+hi=-1294967297 mid=-647483648
  -> java.lang.ArrayIndexOutOfBoundsException: Index -647483648 out of bounds for length 2000000000

Fixed with lo + (hi - lo) / 2: found index 1999999999 after 31 steps. First and last steps:
  lo=0 hi=1999999999 hi-lo=1999999999 mid=999999999
  lo=1000000000 hi=1999999999 hi-lo=999999999 mid=1499999999
  ...
  lo=1999999999 hi=1999999999 hi-lo=0 mid=1999999999

Fixed with (lo + hi) >>> 1: found index 1999999999
