Какова самая быстрая структура данных и / или алгоритм для поиска местоположения вставки в отсортированном числовом списке или массиве без фактической вставки (в c #)

Question

В принципе, каков самый быстрый способ найти место для вставки числа в упорядоченном списке без фактической вставки?Основное беспокойство - эффективность в тесных петлях.

У меня будет список от 1 до 100 значений с плавающей запятой, в большинстве случаев где-то от 20 до 60, поэтому, например, у меня есть:

{0, 1.5f, 10f, 15.6f, 100f}

Если я ввожу значение 1.8f, я хочу получить возвращаемое значение 2. Если я введу значение 20, я хочу получить значение 4, а если я введу 500.2f, я хочу значение 5.

Нет никаких гарантий относительно редкости значений членов списка, но они гарантированно упорядочены правильно.Размер структуры данных не является фактором, только скорость и минимальный сбор мусора.Поэтому, если потенциальное решение требует, чтобы структура данных большего размера или отдельные компоненты списка представляли собой какой-то тип структуры с дополнительной информацией вместо простого плавающего числа, это нормально.

Answer 1

Вы можете использовать List<T>.BinarySearch, если это «упорядоченный список» :

public static int GetInsertIndex<T>(List<T> list, T item)
{
    int nextHigherIndex = list.BinarySearch(item);
    return nextHigherIndex < 0 ? Math.Abs(nextHigherIndex) - 1 : nextHigherIndex + 1;
}

Правила возвращаемого значения BinarySearch:

Начинающийся с нуля индекс элемента в отсортированном List<T>, если элемент найден;в противном случае, отрицательное число, которое является побитовым дополнением индекса следующего элемента, который больше элемента, или, если элемента больше, побитовое дополнение счетчика.

Например:

var list = new List<float>{0, 1.5f,  10f, 15.6f, 100f};
int insertIndex = GetInsertIndex(list, 1.8f);