はじめに
こんにちは、kenです。
今回は「プログラミングで区間を扱いたいときは半開区間が良いよ」という話をします。
もしかしたら有名な事実かもしれませんが、友達にこの話をしたら知らなかったという顔をされたので、自分の理解を深めるためにも記事にすることにしました。
数学で区間を扱う際は実数上で考えることが多いかと思いますが、この記事では区間を考える際、整数全体の集合上での区間を考えることにします。
また以下ではleft（またはl）とright（またはr）という文字式を使って説明しますが、このときleft $ \leq $ rightという関係性は常に満たされているものとします。
半開区間とは？
半開区間の前に、開区間と閉区間についておさらいしておきます。
開区間は(left,right)のように表され、両端点を含まないleftからrightまでの区間を表します。
一方で閉区間は[left,right]のように表され、両端点を含むleftからrightまでの区間を表します。
例えば開区間(1,5)は1と5を含まない1から5までの区間を指すので、2,3,4がこの区間の表す集合となります。
逆に閉区間[1,5]は1と5を含む1から5までの区間を指すので、1,2,3,4,5がこの区間の表す集合となります。
そして、今回紹介したい半開区間はこの２つを組み合わせたような区間です。
半開区間は一般的に[left, right)のような形で表され、leftからrightまでの区間を表しますが、端点はleftを含みrightは含みません。
さっきの例でいくと、[1,5)は1を含み5を含まない1から5までの区間を指すので、1,2,3,4がこの区間の表す集合となります。
半開区間という概念を初めて聞いたという方もいらっしゃるかもしれませんが、きっと今までに触れてきたことがあるはずです。
例えばPythonでfor文を書くときなどに使用されるrange関数は半開区間を使っています。
次のコードのrange(1,5)は先程の記号を用いて表すと[1,5)、つまり1,2,3,4を表しています。
for i in range(1,5):
print("i=%d" % i)
# i=1
# i=2
# i=3
# i=4
半開区間のメリット
一見、中途半端にも思える半開区間ですが、開区間、閉区間よりも良い性質を持っています。
空の区間が表現できる
[a,a)という区間はa以上a未満の区間を表すので、この区間の中には要素が存在しません。つまり空の区間です。
空の区間の表現は閉区間でやろうとするとうまくいきません。
一応left $ \leq $ rightという関係性を無視して[a,a-1]というように書けば空の区間にはなりますが、左右の大小関係が逆転しているのは気持ちが悪いです。
区間内の個数を数えやすい
半開区間の場合[left,right)に含まれる要素の数は、right-leftで求めることができます。
開区間(left,right)の場合だとright - left - 1、閉区間[left,right]の場合だとright - left + 1となるので、余計な$\pm$1がついてしまいややこしいです。
分割がしやすい
半開区間[left, right)をmidを境目として2つの区間に分割する場合は[left,mid)と[mid,right)というように書けます。
しかし開区間(left,right)でこの分割をしようとすると(left,mid)と(mid-1,right)となってしまい分割されてる感が伝わりにくいですね。
閉区間[left,right]でも[left,mid-1]と[mid,right]となってしまい、やはり余計な$\pm$1がついてしまいます。
区間同士の隣接がわかりやすい
2つの区間があったとき、その端と端を繋げて1つの区間にできるかということを考えてみます。
例えば区間Aが1,2を、区間Bが3,4,5を表している場合、この区間Aと区間Bをつなげると1,2,3,4,5とひとまとまりの区間になるので区間Aと区間Bはいわば隣接しているといえます。
半開区間だと[left,mid1)と[mid2,right)が隣接しているかどうかはmid1 = mid2で判定できます。
一方で開区間(left,mid1)と(mid2,right)が隣接しているかどうかはmid1 + 1 = mid2となり、またもや余計な+1が入ってきます。
まとめ
確かに半開区間には開区間や閉区間より良い性質があることがわかりました。
絶対的に区間は半開区間で表したほうが良いということではありませんが、このような良い性質があるということは頭の片隅においておいたほうが良いかもしれません。
間違いなどありましたらコメントにてご指摘ください、ここまで読んでいただきありがとうございました。