プログラミングにおける「半開区間」

はじめに

プログラム中では、区間は 閉区間 や 半開区間 など様々な方法で扱うことができます。
扱い方によって実現できる処理が変わることはありませんが、意識的に統一しておかなければバグを生む要因となります。

区間の扱いかたのうち、半開区間の特徴をまとめたのが本記事です。
具体的には、半開区間の

1. 区間の長さ判定
2. 区間の分割方法
3. 区間の包含判定
4. 区間の交差判定
5. 区間の隣接判定

について述べています。

※なおここでは整数値によって表現される区間を対象とします。

半開区間とは

[a,b)で表される区間を左閉右開区間(左閉半開区間)と言い、
(a,b]で表される区間を左開右閉区間(右閉半開区間)と言います。
これらを合わせて半開区間と呼びます。
※角括弧と丸括弧の意味の違いの説明はここでは省略します

この記事では、競技プログラミングにおいてもよく利用されている[a,b)(左閉右開区間)について扱います。

記号の定義

本記事では区間(segment)を と表し、添字は識別子を表します。
区間の情報は [l,r) で表し、区間 の情報は [) です。

特徴

区間の長さ

区間 の長さは r - l と等しくなります。

区間の分割

区間 [l,r) を、c-1とcの間を境界として分割すると、[l,c) と [c,r) の2つの区間ができます。
(閉区間で同様の事を行うと、[l,r-1] -> [l,c-1]と[c,r-1] となり少しややこしいです。)

区間の包含関係

かつ のとき、 は に包含されています。

区間の交差判定

または のとき、 と は交差しています。

ある2区間 と が隣接しているかの判定

または のとき、 と は隣接しています。

まとめ

半開区間は、区間の長さを調べたり区間を分割するときに便利です。
二分探索でも多くの場合半開区間を用いているので、このあたりをおさらいしておくと何かの役に立つかもしれません。