Список инверсий
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В информатике инверсионный список — это структура данных , описывающая набор непересекающихся числовых диапазонов, хранящихся в порядке возрастания.
Набор хранится в массиве . Каждый второй элемент является первым элементом диапазона, а каждый второй элемент — первым элементом после этого диапазона (полуоткрытый диапазон).
Например, для диапазонов 10–14, 25–37 список инверсий будет таким:
10 15 25 38
Чтобы определить, принадлежит ли элемент какому-либо из диапазонов, бинарный поиск выполняется . Если поиск заканчивается на «первом» элементе, искомый элемент находится в наборе. Если поиск заканчивается элементом «после» или вне массива, искомый элемент отсутствует в наборе.
Эта структура данных используется во многих реализациях Unicode для хранения диапазонов символов Unicode (например, «греческих символов»).