Zenn
😎

lower_bound,upper_bound図解

2023/06/06に公開
C++
tech

要約

  • lower_bound,upper_boundは配列等を大きい部分と小さい部分に2分割する（ための境界を得る）関数とみればよい。
  • 分割するしきい値はlower_boundだとvalueの下,upper_boundだとvalueの上にくる。
  • 分割可能なら適用できるから、完全にはソートされてない配列等にも使える。

本題

ここではそれぞれlower_bound(配列等,value),upper_bound(配列等,value)としておく。
与える引数を

vector<int> array ={1,2,1,4,5,6,5};
int value=3;

として、

lower_bound(array,value)
upper_bound(array,value)

のときを例に説明する。

図の説明

  • 横軸がindex、縦軸が値

lower_bound

しきい値はvalue=3の下にくる。返り値はindex=3にあたるイテレータ。スライス操作[1]だと"分割する"という意味がわかりやすいと思う。つまり図の下はarray[:3](ind=0,1,2)、上はarray[3:](ind=3,4,5,...)にあたり、元のarrayが分割されている。返り値(=3)が上下のarrayの境界(boundary)になっていることが分かる。

upper_bound

しきい値がvalue=3の上にくることを除いて同じ。
返り値はindex=5にあたるイテレータ。図の下はarray[:5](ind=0,1,2,3,4)、上はarray[5:](ind=5,6,...)にあたる。返り値(=5)が上下のarrayの境界(boundary)になっていることが分かる。

後書き

しきい値がlower_boundだとvalueの下,upper_boundだとvalueの上にくるからlowと下、upと上が対応してるのがスッキリ分かる。
なにか間違えてたら教えてね😎

参考文献

lower_bound https://cpprefjp.github.io/reference/algorithm/lower_bound.html
upper_bound https://cpprefjp.github.io/reference/algorithm/upper_bound.html
もっときっちりした解説 https://rsk0315.hatenablog.com/entry/2022/08/12/130515#fn-e8b3f09b

脚注

  1. Goのスライス操作を想定 ↩︎

Discussion