lower_bound, upper_bound, 결국 어느 쪽을 사용하면 좋을까? 라는 장면이 많았기 때문에, 메모가 테라에 써 본다. 이 기사에서는 직관적으로 lower_bound나 upper_bound가 잘 다룰 수 있게 되는 것을 목표로 한다. 예를 들어,

vector<int> v = {40, 20, 20, 19, 1};

와 내림차순으로 배열되는 배열에 대해 41, 40, 39, 21, 20, 19, 18, 2, 1, 0 등을 key로 했을 때, lower_bound, upper_bound를 어떻게 사용하면 좋을까, 그리고 그것이 어디의 이터레이터 을 돌려줄지 곧 모르는 사람을 향한 기사가 된다. 어디까지나 하나의 기억 방법인 것에 유의해 주었으면 한다.

주의사항(잘못해도 좋다)

전제로서 이번에 사용하는 컨테이너는 vector이다. 또한 배열은 이미 sorted라고 가정합니다. C++11부터 sort 끝나지 않아도 있는 기준을 충족하고 있다면 lower_bound나 upper_bound를 사용할 수 있다( 참고: htps : // cpp fjp. 기주 b. 이오/레후오렌세/아 l고리 thm/ぉ우ぇr_보응 d. HTML ) 하지만 이번에는 무시한다.

오름차순 배열에 대한 사용법

vector<int> v = {1, 1, 1, 2, 2, 3, 3, 3, 5};

에 대해서 사용해 본다. 예를 들어 2를 키로 이분 탐색하려면 간단히

lower_bound(v.begin(), v.end(), 2);
upper_bound(v.begin(), v.end(), 2);

하면 된다. 그리고 이것들은 무엇을 반환할 것인가? 다음과 같이 생각하면 이해하기 쉽습니다.

키를 인터럽트하고, 나머지를 오른쪽으로 옮겼을 때, 배열은 sort 된 채로 있는 것 같은 위치의 이터레이터를 돌려준다. 그리고 lower_bound는 그러한 위치 중에서 가장 왼쪽 (따라서 lower), upper_bound는 가장 오른쪽 (따라서 upper)의 위치를 ​​반환한다.

다음 그림을 보면 알 수 있다고 생각한다(key = 0, 1, 2, 3, 4, 5, 6).
key=0일 때


key=1일 때


key=2일 때


key=3일 때


key=4일 때


key=5일 때


key=6일 때


gif


말을 간결하게 하면, sort 끝난 배열의 순서를 무너뜨리지 않게 key를 넣을 때, 최좌(또는 최우)로 어디에 넣을 수 있는지를 돌려준다고 하는 것이다.
이 기억의 장점은, 「이상」 「보다 크다」라고 하는 말에 의지하지 않고 흩어지기 때문에 v.end()가 언제 돌아올까? 등 직관적으로 알고, 게다가 lower나 upper라는 이름도 이해에 연결된다. 또한 내림차순 배열에도 lower_bound와 upper_bound를 사용할 수 있습니다.

내림차순 배열에 대한 사용법

vector<int> v = {5, 3, 3, 3, 2, 2, 1};

에 대해서 사용해 본다. 예를 들어 2를 키로 이분 탐색하려면,

lower_bound(v.begin(), v.end(), 2, greater<int>());
upper_bound(v.begin(), v.end(), 2, greater<int>());

하면 된다. 네 번째 인수는 "배열이 어떻게 sorted되는가?"를 lower_bound, upper_bound에 전달하는 역할을 하고 있다(여기서는 greater, 즉 >이므로 내림차순). 기본적으로 오름차순이라고 가정합니다. 앞 장을 근거로 하면 내림차순 배열의 순서를 무너뜨리지 않도록 key를 넣을 때 가장 왼쪽(또는 가장 오른쪽)으로 어디에 넣을 수 있는지를 돌려주는 것을 알 수 있다. 그렇다면 key = 2 일 때 lower_bound는 v [4]의 반복자를 반환하고 upper_bound는 v [6]의 반복자를 반환한다는 것을 쉽게 알 수 있습니다.