Постоянный алгоритм поиска для равномерно распределенных массивов?

Question

Я искал хороший алгоритм поиска и столкнулся с поиском с интерполяцией, который имеет временную сложность O (log (log (n))) и может применяться только к равномерно распределенным массивам. Но я обнаружил, что было возможно создать алгоритм поиска, который требует тех же условий, но имеет временную сложность O (1). Вот что я придумал: (код на C ++)

int search(double Find, double* Array, const int Size) {
    if (Array[0] == Array[1] && Find == Array[0]) { return 0; }
    if (Array[0] == Array[1] && Find != Array[0]) { return -1; }
    const double Index = (Find - Array[0]) / (Array[Size - 1] - Array[0]) * (Size - 1.0);
    if (Index < 0 || Index >= Size || Array[(int)(Index + 0.5)] != Find) { return -1; }
    return Index + 0.5; 
}

В этой функции мы передаем число, которое мы хотим найти, указатель массива и размер массива. Эта функция возвращает индекс, где находится номер, который нужно найти, или -1, если не найден.

Объяснение: Ну, объяснить это без картинки будет сложно, я буду стараться изо всех сил ...

Поскольку массив распределен равномерно, мы можем представить все его значения на графике, с индексом (скажем, х) как абсцисса, и значением, содержащимся в массиве в этом индексе (скажем, Arr [x]) как ордината. Итак, мы можем видеть, что все точки, представленные на графике, принадлежат функции уравнения:

Array [x] = tan (A) * x + Arr [0] -> с A в качестве сформированного угла между функцией и осью X графика.

Итак, теперь мы можем преобразовать уравнение в:

x = (Arr [x] - Arr [0]) / tan ( А)

И все, х - это индекс, который нужно найти по отношению к Arr [x] (заданное значение для поиска). Мы можем просто изменить формулу на x = (Arr [x] - Array [0]) / (Array [Size - 1] - Array [0]) * (Size - 1.0), потому что мы знаем, что tan (A) = ( Массив [Размер - 1] - Массив [0]) / (Размер - 1,0).

Вопрос (Окончательно ...)

Полагаю, что эта формула уже используется в некоторых программах, его было довольно легко найти ... Итак, мой вопрос: зачем использовать поиск интерполяции вместо этого? Я что-то не понимаю?

Спасибо за терпение и помощь.

Answer 1

Говоря о равномерном распределении, это не означает, что, когда вы знаете первое и последнее значение в отсортированном массиве, вы также знаете другие значения. Это то, что предполагает ваш алгоритм. Равномерное распределение связано с вероятностями, связанными с созданием массива, но в реальных массивах, созданных по этому принципу равномерного распределения, вы все равно можете получить массивы, которые выглядят не столь равномерно распределенными. Это вопрос вероятности. В среднем значения будут равномерно распределены, но это не является гарантией.

Во-вторых, ваш алгоритм фактически является алгоритмом интерполяции, с той разницей, что он предполагает, что после первого поиска он должен был прийти к место, где должно быть значение. Тем не менее, в случайно созданных массивах (равномерно распределенных) это не гарантируется, и поэтому операция должна повторяться на меньшем интервале, пока интервал не сойдет к одному индексу.

См. Также:

• CS: Что означает равномерное распределение элементов в массиве?
• Википедия: Равномерное распределение