Integer Overflow in Midpoint

Problem

This search was prototyped in Python against a sorted array of sensor readings and worked for months. It was then ported line-for-line to Java (where int is a signed 32-bit integer) to run inside the ingestion service, which holds about 1.5 billion readings in one array. The Java version crashes on some lookups with java.lang.ArrayIndexOutOfBoundsException: Index -847483648 out of bounds for length 1500000000. The Python original:

def index_of(readings: list[int], target: int) -> int:
    lo, hi = 0, len(readings) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if readings[mid] == target:
            return mid
        if readings[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Why does the Java port crash when the Python does not? Which line is wrong, and what should the port say? Fix the Python so that the fixed version is safe to port to any language.

Examples

• readings = [3, 8, 15, 21], target = 15 → 2 in both languages. Small arrays never trigger the bug.
• Array of 1,500,000,000 elements, target near the end. After a few iterations lo ≈ 1.1e9 and hi ≈ 1.5e9. In Python mid = 1.3e9, fine. In 32-bit arithmetic lo + hi = 2,600,000,000 exceeds 2^31 - 1 = 2,147,483,647 and wraps to 2,600,000,000 - 2^32 = -1,694,967,296; Java's / 2 truncates toward zero, so mid = -847,483,648, the index in the exception.
• Any array of at most 2^30 = 1,073,741,824 elements is safe even with the buggy expression, because lo + hi < 2^31. That is why the bug hid until the array grew.

Hints

1. What is the largest value lo + hi can take, in terms of the array length? Compare it with the largest 32-bit signed integer.
2. Python integers are arbitrary precision. Which of the intermediate values in the loop would not fit in 32 bits?
3. Rewrite the midpoint so that no intermediate value is larger than hi.