Какая структура данных лучше всего подходит для поиска и обновления целочисленных значений массива?

Question

Если у меня есть массив как [7, 11, 13, 9, 4, 6], а пользовательский ввод - 10,
я хочу, чтобы целое число чуть выше (или равное) 10 (в данном случае 11) и заменило его целым числом - 10 (11 - 10)
Я не могу упорядочить список и бинарный поиск, так как мне нужно вернуть индекс обновленного элемента.
Я посмотрел на упорядочивание пар (индекс, целое число), а затем на двоичный поиск, но после обновления мне нужно пересортировать массив пар для следующего ввода пользователя.

исходный массив = [7, 11, 13, 9, 4, 6]
отсортированный массив = [4, 6, 7, 9, 11, 13]
пользовательский ввод = 10
вывод = 1 (индекс обновленного целого числа)

обновленный отсортированный массив = [4, 6, 7, 9, 1, 13]
повторно отсортированный массив = [1, 4, 6, 7, 9, 13]
пользовательский ввод = 4
...

Какая структура данных будет подходящей для реализации этого?

Answer 1

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

Операции с упорядоченным множеством включают:

1. Добавьте элемент.
2. Удалить элемент.
3. Найдите элемент.
4. Искать элемент, больший или равный заданному.
5. Искать элемент больше заданного.

Данная проблема может быть решена с помощью упорядоченного набора операций, описанных выше.

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

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