Вопрос такой: 

Как должны быть упорядочены элементы при использовании интерполяционного поиска - 


строго: A1<A2<A3<... (A1>A2>A3<...)

Или всё же так : A1<=A2<=A3<=...  (A1>=A2>=A3>=...) ?


Напомню что при интерполяц. поиске  M = L + (R - L)*(x - a[L])/(a[R] - a[L]).

И тогда ведь возможно, что если допускаются равные эл-ты, то здесь (a[R] - a[L]) возможно может получиться 0 и тогда будет деление на 0? Или я где-то ошибаюсь?

можно нестрого
только нужно удостовериться, что проверка на a[L]==x находится до вычисления M
а если a[L]<=x<=a[R] и a[L]==a[R], то обязательно получится a[L]==x