search/InterpolationSearch: integer / by zero crash when arr[hi]==arr[lo] (e.g. searching the max element); division done before multiplication

[aimasteracc]

Description

src/main/kotlin/search/InterpolationSearch.kt::interpolationSearch has two bugs in its probe-position computation:

pos = (lo
        + ((hi - lo) / (arr[hi] - arr[lo])
        * (x - arr[lo])))

1. Integer division by zero → crash (ArithmeticException: / by zero).
When arr[hi] == arr[lo], the divisor arr[hi] - arr[lo] is 0. Because everything here is Int, this throws ArithmeticException instead of returning a result. This happens routinely:

• whenever the search range narrows to a single element (lo == hi), which always occurs when searching for the maximum element of a distinct-valued array, and
• whenever the endpoints are equal (arrays with duplicate values).

Trace for interpolationSearch(intArrayOf(10, 20, 30), 0, 2, 30):

• lo=0, hi=2: pos = 0 + (2/(30-10))*(30-10) = 0 → arr[0]=10 < 30 → recurse (1, 2)
• lo=1, hi=2: pos = 1 + (1/(30-20))*(30-20) = 1 → arr[1]=20 < 30 → recurse (2, 2)
• lo=2, hi=2: enters the if (30 is in [30,30]), divisor arr[2]-arr[2] = 0 → / by zero crash

So searching for the largest present element crashes instead of returning its index (2).

2. Integer division performed before multiplication → wrong/degenerate probe.
The standard interpolation formula is lo + ((x - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]) — multiply first, then divide. This code divides first: (hi - lo) / (arr[hi] - arr[lo]), which in integer arithmetic is 0 almost always (the index span is tiny next to the value span), so pos collapses to lo. The interpolation degrades to a linear scan (defeating the O(log log n) purpose), and the probe is mathematically wrong.

Expected behavior

interpolationSearch(intArrayOf(10, 20, 30), 0, 2, 30) returns 2; searching arrays with duplicate values does not crash.

Actual behavior

It throws ArithmeticException: / by zero for the single-element / equal-endpoint case (including searching the max element), and otherwise probes at lo due to premature integer division.

Suggested fix

Multiply before dividing and guard the zero denominator:

if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
    if (arr[hi] == arr[lo]) {            // single distinct value in range
        return if (arr[lo] == x) lo else -1
    }
    val pos = lo + ((x - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo])
    ...
}