Half-open interval - Revision history

Brian at 02:56, 14 May 2012

2012-05-14T02:56:39Z

Brian at 08:11, 15 December 2011

2011-12-15T08:11:27Z

Brian at 23:05, 22 November 2011

2011-11-22T23:05:04Z

Brian: Created page with "A '''left half-open interval''' is an interval of the form $[a,b)$ ; it contains all $x$ such that $a \leq x < b$ . It is often useful to express p..."

2011-11-21T17:19:56Z

Created page with "A '''left half-open interval''' is an interval of the form <math>[a,b)</math>; it contains all <math>x</math> such that <math>a \leq x < b</math>. It is often useful to express p..."

New page

A '''left half-open interval''' is an interval of the form <math>[a,b)</math>; it contains all <math>x</math> such that <math>a \leq x < b</math>. It is often useful to express problems, [[algorithm]]s, [[data structure]]s, and library functions in terms of left half-open intervals of integers; a segment of an array is then specified by giving the left endpoint, that is, the index to the first element in the segment, and the right endpoint, which is the element ''just after'' the last element in the segment. For example, in C++, to sort a segment of an array <code>A</code> from the third element to the sixth element, inclusive, the code is <code>std::sort(A+3, A+7);</code>. The STL containers <code>std::vector</code>, <code>std::list</code>, <code>std::deque</code>, <code>std::set</code>, and <code>std::map</code> all have two member functions, <code>begin()</code> and <code>end()</code>, where the latter returns an iterator, not to the actual last element in the container, but to an imaginary element "just past the end".

Left half-open intervals are convenient because they have the following desirable properties:
* The interval of length <math>n</math> starting at <math>i</math> can simply be denoted <math>[i,i+n)</math>, rather than the more cumbersome <math>[i,i+n-1]</math>.
* The ''disjoint'' union of <math>[i,j)</math> and <math>[j,k)</math> is <math>[i,k)</math>; and likewise any left half-open interval <math>[a,b)</math> may be divided by intermediate values <math>a < c_0 < c_1 < ... < c_n < b</math> into a disjoint union of left half-open intervals <math>[a,c_0) \cup [c_0,c_1) \cup [c_1,c_2) \cup ... \cup [c_n, b)</math>; ''i.e.'', endpoints telescope nicely with half-open intervals, whereas they do not with fully open or fully closed intervals.

Here is an example of when left half-open intervals may be useful. We usually think of one-dimensional [[array]]s as being lines of boxes, where each box represents an element. Sometimes, we want to use a one-dimensional array to store some information about exact points in time; maybe something happens exactly at ''t'' = 15 s and ends exactly at ''t'' = 21 s. A second is an interval delineated by two points (that are, by definition, one second apart); a second is like a box, but a point in time is like one of the lines that separates two boxes. We can represent the interval in time between 15 s and 21 s as the half-open interval [15, 21); that is, identify each box in the array with the point of time when it ''starts''. Since the last second of the event is between 20 s and 21 s (instead of 21 s and 22 s), the box at index 21 is not used.

The choice of left half-open intervals over right half-open intervals is arbitrary, but appears to be a ''de facto'' standard.

@@ Line 1: / Line 1: @@
-A '''left half-open interval''' is an interval of the form <math>[a,b)</math>; it contains all <math>x</math> such that <math>a \leq x < b</math>. It is often useful to express problems, [[algorithm]]s, [[data structure]]s, and library functions in terms of left half-open intervals of integers; a segment of an array is then specified by giving the left endpoint, that is, the index to the first element in the segment, and the right endpoint, which is the element ''just after'' the last element in the segment. For example, in C++, to sort a segment of an array <code>A</code> from the third element to the sixth element, inclusive, the code is <code>std::sort(A+3, A+7);</code>. The STL containers <code>std::vector</code>, <code>std::list</code>, <code>std::deque</code>, <code>std::set</code>, and <code>std::map</code> all have two member functions, <code>begin()</code> and <code>end()</code>, where the latter returns an iterator, not to the actual last element in the container, but to an imaginary element "just past the end".
+A '''right half-open interval''' (less commonly ''left half-closed interval'') is an interval of the form <math>[a,b)</math>; it contains all <math>x</math> such that <math>a \leq x < b</math>. It is often useful to express problems, [[algorithm]]s, [[data structure]]s, and library functions in terms of right half-open intervals of integers; a segment of an array is then specified by giving the left endpoint, that is, the index to the first element in the segment, and the right endpoint, which is the element ''just after'' the last element in the segment. For example, in C++, to sort a segment of an array <code>A</code> from the third element to the sixth element, inclusive, the code is <code>std::sort(A+3, A+7);</code>. The STL containers <code>std::vector</code>, <code>std::list</code>, <code>std::deque</code>, <code>std::set</code>, and <code>std::map</code> all have two member functions, <code>begin()</code> and <code>end()</code>, where the latter returns an iterator, not to the actual last element in the container, but to an imaginary element "just past the end".
-Left half-open intervals are convenient because they have the following desirable properties:
+Right half-open intervals are convenient because they have the following desirable properties:
 * The interval <math>[a,b)</math> contains <math>b-a</math> elements exactly (rather than <math>b-a+1</math> or <math>b-a-1</math>).
 * The interval of length <math>n</math> starting at <math>i</math> can simply be denoted <math>[i,i+n)</math>, rather than the more cumbersome <math>[i,i+n-1]</math>.
-* The ''disjoint'' union of <math>[i,j)</math> and <math>[j,k)</math> is <math>[i,k)</math>; and likewise any left half-open interval <math>[a,b)</math> may be divided by intermediate values <math>a < c_0 < c_1 < ... < c_n < b</math> into a disjoint union of left half-open intervals <math>[a,c_0) \cup [c_0,c_1) \cup [c_1,c_2) \cup ... \cup [c_n, b)</math>; ''i.e.'', endpoints telescope nicely with half-open intervals, whereas they do not with fully open or fully closed intervals.
+* The ''disjoint'' union of <math>[i,j)</math> and <math>[j,k)</math> is <math>[i,k)</math>; and likewise any right half-open interval <math>[a,b)</math> may be divided by intermediate values <math>a < c_0 < c_1 < ... < c_n < b</math> into a disjoint union of right half-open intervals <math>[a,c_0) \cup [c_0,c_1) \cup [c_1,c_2) \cup ... \cup [c_n, b)</math>; ''i.e.'', endpoints telescope nicely with half-open intervals, whereas they do not with fully open or fully closed intervals.
 * See also [[prefix sum array and difference array]].
-Here is an example of when left half-open intervals may be useful. We usually think of one-dimensional [[array]]s as being lines of boxes, where each box represents an element. Sometimes, we want to use a one-dimensional array to store some information about exact points in time; maybe something happens exactly at ''t'' = 15 s and ends exactly at ''t'' = 21 s. A second is an interval delineated by two points (that are, by definition, one second apart); a second is like a box, but a point in time is like one of the lines that separates two boxes. We can represent the interval in time between 15 s and 21 s as the half-open interval [15, 21); that is, identify each box in the array with the point of time when it ''starts''. Since the last second of the event is between 20 s and 21 s (instead of 21 s and 22 s), the box at index 21 is not used.
+Here is an example of when right half-open intervals may be useful. We usually think of one-dimensional [[array]]s as being lines of boxes, where each box represents an element. Sometimes, we want to use a one-dimensional array to store some information about exact points in time; maybe something happens exactly at ''t'' = 15 s and ends exactly at ''t'' = 21 s. A second is an interval delineated by two points (that are, by definition, one second apart); a second is like a box, but a point in time is like one of the lines that separates two boxes. We can represent the interval in time between 15 s and 21 s as the half-open interval [15, 21); that is, identify each box in the array with the point of time when it ''starts''. Since the last second of the event is between 20 s and 21 s (instead of 21 s and 22 s), the box at index 21 is not used.
-The choice of left half-open intervals over right half-open intervals is arbitrary, but appears to be a ''de facto'' standard.
+The choice of right half-open intervals over left half-open intervals is arbitrary, but appears to be a ''de facto'' standard.

Half-open interval - Revision history

Brian at 02:56, 14 May 2012

Brian at 08:11, 15 December 2011

Brian at 23:05, 22 November 2011

Brian: Created page with "A '''left half-open interval''' is an interval of the form [a,b); it contains all x such that a \leq x < b. It is often useful to express p..."

Brian: Created page with "A '''left half-open interval''' is an interval of the form $[a,b)$ ; it contains all $x$ such that $a \leq x < b$ . It is often useful to express p..."