This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (December 2015)
In computer science, an inversion list is a data structure that describes a set of non-overlapping numeric ranges, stored in increasing order.
The set is stored in an array. Every other element is the first element of a range, and every other element is the first element after that range (a half-open range).
For example, for ranges 10-14, 25-37, the inversion list would be:
10 15 25 38
To search whether an item belongs to any of the ranges, a binary search is made. If the search ends in a "first" element, the searched item is in the set. If the search ends in an "after" element, or outside the array, the searched item is not in the set.
This data structure is used in many Unicode implementations for storing Unicode character ranges (like "Greek characters").
inversion, list, confused, with, inverted, index, this, article, multiple, issues, please, help, improve, discuss, these, issues, talk, page, learn, when, remove, these, template, messages, this, article, orphan, other, articles, link, please, introduce, links. Not to be confused with Inverted index This article has multiple issues Please help improve it or discuss these issues on the talk page Learn how and when to remove these template messages This article is an orphan as no other articles link to it Please introduce links to this page from related articles try the Find link tool for suggestions December 2015 This article does not cite any sources Please help improve this article by adding citations to reliable sources Unsourced material may be challenged and removed Find sources Inversion list news newspapers books scholar JSTOR March 2022 Learn how and when to remove this template message Learn how and when to remove this template message In computer science an inversion list is a data structure that describes a set of non overlapping numeric ranges stored in increasing order The set is stored in an array Every other element is the first element of a range and every other element is the first element after that range a half open range For example for ranges 10 14 25 37 the inversion list would be 10 15 25 38To search whether an item belongs to any of the ranges a binary search is made If the search ends in a first element the searched item is in the set If the search ends in an after element or outside the array the searched item is not in the set This data structure is used in many Unicode implementations for storing Unicode character ranges like Greek characters External links EditUnicode Demystified Google Books snippet pages 504 Unicode UCD Perl module Retrieved from https en wikipedia org w index php title Inversion list amp oldid 1101401624, wikipedia, wiki, book, books, library,
