interpolationSearch may not return the first index with the value

[dubzzz]

Details:

Behaviour of interpolationSearch may be considered inconsistent.
For some arrays it will return the index of the first match - expect(interpolationSearch([1, 1], 1)).toBe(0) - while for others it returns the second or third one.

Step to reproduce: interpolationSearch([-1, 0, 0], 0))
Expected result: 1
Got: 2

How did I find it?

Thanks to property based testing framework fast-check.
The property was the following:

import fc from 'fast-check';

fc.assert(
  fc.property(
    fc.array(fc.integer()).map(arr => [...arr].sort((a, b) => a - b)),
    fc.integer(),
    (arr, i) => expect(interpolationSearch(arr, i)).toBe(arr.indexOf(i))
  )
)

Or:

for any arr - sorted array of integers - and i - integer value
interpolationSearch(arr, i) should be equivalent to arr.indexOf(i)