std :: lower_bound 및 std :: upper_bound의 이론적 근거?

std :: lower_bound 및 std :: upper_bound의 이론적 근거?

---

STL은 이진 검색 기능 std :: lower_bound 및 std :: upper_bound를 제공하지만 계약 내용이 완전히 미스터리하게 보이기 때문에 그들이하는 일을 기억할 수 없기 때문에 사용하지 않는 경향이 있습니다.

이름을 살펴보면 "lower_bound"가 "last lower bound"의 줄임말 일 수 있다고 생각합니다.
즉, 정렬 된 목록에서 <= 주어진 val (있는 경우) 인 마지막 요소입니다.
그리고 비슷하게 "upper_bound"가 "first upper bound"의 줄임말 일 수 있다고 생각합니다.
즉, 정렬 된 목록에서> = 주어진 val (있는 경우) 인 첫 번째 요소입니다.

그러나 문서는 그들이 그것과는 다소 다른 일을한다고 말합니다. 저에게는 역방향과 무작위가 혼합 된 것처럼 보입니다. 문서를 의역하기 위해 :
-lower_bound는> = val 인
첫 번째 요소를 찾습니다.-upper_bound는> val 인 첫 번째 요소를 찾습니다.

따라서 lower_bound는 하한을 전혀 찾지 못합니다. 첫 번째 상한을 찾습니다 !? 그리고 upper_bound는 첫 번째 엄격한 상한을 찾습니다 .

이게 말이 되나요 ?? 어떻게 기억하십니까?

---

값 이 검색중인 값과 같은 [ first, last) 범위에 여러 요소가있는 val경우 범위 [ l, u) 여기서

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

정확히 val[ first, last) 범위 내에서 동일한 요소 범위입니다 . 따라서 l및 u은 "하한"하고는 "상한" 동등한 범위 . 반 개방 간격으로 생각하는 데 익숙하다면 의미가 있습니다.

(단 std::equal_range한 번의 호출에서 한 쌍의 하한과 상한을 모두 반환합니다.)

---

std::lower_bound

값 보다 작지 않은 (즉, 크거나 같은 ) 범위 [first, last)의 첫 번째 요소를 가리키는 반복기를 리턴합니다 .

std::upper_bound

값 보다 큰 [first, last) 범위의 첫 번째 요소를 가리키는 반복기를 반환합니다 .

따라서 하한과 상한을 모두 혼합하면 범위가 시작되는 위치와 끝나는 위치를 정확하게 설명 할 수 있습니다.

이게 말이 되나요 ??

예.

예:

벡터 상상

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                  // ^ lower

auto upper = std::upper_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                           // ^ upper

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

인쇄 : 44 4

---

http://en.cppreference.com/w/cpp/algorithm/lower_bound

http://en.cppreference.com/w/cpp/algorithm/upper_bound

---

이 경우 사진은 천 마디 말의 가치가 있다고 생각합니다. 2다음 컬렉션에서 검색하는 데 사용한다고 가정 해 보겠습니다 . 화살표는 두 가지가 반환하는 반복기를 보여줍니다.

따라서 컬렉션에 이미 해당 값이있는 개체가 두 개 이상 lower_bound있는 경우 첫 번째 항목 upper_bound을 참조하는 반복기를 제공하고 마지막 항목 바로 뒤에있는 개체를 참조하는 반복기를 제공합니다.

이것은 (다른 것들 중에서) 반환 된 이터레이터를에 대한 hint매개 변수로 사용할 수있게합니다 insert.

따라서이를 힌트로 사용하면 삽입 한 항목이 해당 값 (을 사용한 경우 lower_bound) 또는 해당 값을 가진 마지막 항목 (을 사용한 경우 ) 의 새 첫 번째 항목 이됩니다 upper_bound. 컬렉션에 이전에 해당 값이있는 항목이 포함되지 않은 경우 컬렉션 hint의 올바른 위치에 삽입하는 데 사용할 수있는 반복기를 계속 얻을 수 있습니다 .

물론 힌트없이 삽입 할 수도 있지만 힌트를 사용하면 삽입 할 새 항목을 반복자가 가리키는 항목 바로 앞에 삽입 할 수있는 경우 삽입이 일정한 복잡성으로 완료된다는 것을 보장 할 수 있습니다. 이 두 경우 모두).

---

순서를 고려하십시오

12 34 5 6 6678 9

6의 하한은 처음 6의 위치입니다.

6의 상한은 7의 위치입니다.

이러한 위치는 6 개 값의 실행을 지정하는 공통 (시작, 끝) 쌍으로 사용됩니다.

---

예:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

auto main()
    -> int
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
    auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
    auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
    for( auto it = pos1; it != pos2; ++it )
    {
        cout << *it;
    }
    cout << endl;
}

---

나는 브라이언의 대답을 받아 들였지만, 나에게 명확성을 더해주는 또 다른 유용한 사고 방식을 깨달았 기 때문에 이것을 참조 용으로 추가했습니다.

Think of the returned iterator as pointing, not at the element *iter, but just before that element, i.e. between that element and the preceding element in the list if there is one. Thinking about it that way, the contracts of the two functions become symmetric: lower_bound finds the position of the transition from <val to >=val, and upper_bound finds the position of the transition from <=val to >val. Or to put it another way, lower_bound is the beginning of the range of items that compare equal to val (i.e. the range that std::equal_range returns), and upper_bound is the end of them.

I wish they would talk about it like this (or any of the other good answers given) in the docs; that would make it much less mystifying!

---

Both functions are very similar, in that they will find an insertion point in a sorted sequence that will preserve the sort. If there are no existing elements in the sequence that are equal to the search item, they will return the same iterator.

If you're trying to find something in the sequence, use lower_bound - it will point directly to the element if it's found.

If you're inserting into the sequence, use upper_bound - it preserves the original ordering of duplicates.

---

the source code actually has a second explanation which I found very helpful to understand the meaning of the function:

lower_bound: Finds the first position in which [val] could be inserted without changing the ordering.

upper_bound: Finds the last position in which [val] could be inserted without changing the ordering.

this [first, last) forms a range which the val could be inserted but still keep the original ordering of the container

lower_bound return "first" i.e. find the "lower boundary of the range"

upper_bound return "last" i.e. find the "upper boundary of the range"

---

There are already good answers as to what std::lower_bound and std::upper_boundis.

I would like to answer your question 'how to remember them'?

Its easy to understand/remember if we draw an analogy with STL begin() and end() methods of any container. begin() returns the starting iterator to the container while end() returns the iterator which is just outside the container and we all know how useful they are while iterating.

Now, on a sorted container and given value, lower_boundand upper_bound will return range of iterators for that value easy to iterate on (just like begin and end)

Practical usage::

Apart form the above mentioned usage on sorted list to access the range for a given value, one of the better applications of upper_bound is to access data having many-to-one relationship in a map.

For example, consider the following relationship: 1 -> a, 2 -> a, 3 -> a, 4 -> b, 5 -> c, 6 -> c, 7 -> c , 8 -> c, 9 -> c, 10 -> c

The above 10 mappings can be saved in map as follows:

numeric_limits<T>::lowest() : UND
1 : a
4 : b
5 : c
11 : UND

The values can be access by the expression (--map.upper_bound(val))->second.

For values of T ranging from lowest to 0, the expression will return UND. For values of T ranging from 1 to 3, it will return 'a' and so on..

Now, imagine we have 100s of data mapping to one value and 100s of such mappings. This approach reduces the size of the map and thereby making it efficient.

---

Yes. The question absolutely has a point. When someone gave these functions their names they were thinking only of sorted arrays with repeating elements. If you have an array with unique elements, "std::lower_bound()" acts more like a search for an "upper bound" unless it finds the actual element.

So this is what I remember about these functions:

• If you are doing a binary search, consider using std::lower_bound(), and read the manual. std::binary_search() is based on it, too.
• If you want to find the "place" of a value in a sorted array of unique values, consider std::lower_bound() and read the manual.
• If you have an arbitrary task of searching in a sorted array, read the manual for both std::lower_bound() and std::upper_bound().

Failing to read the manual after a month or two since you last used these functions, almost certainly leads to a bug.

---

Imagine what you would do if you want to find the first element equal to val in [first, last). You first exclude from first elements which are strictly smaller than val, then exclude backward from last - 1 those strictly greater than val. Then the remaining range is [lower_bound, upper_bound]

---

For an array or vector :

std :: lower_bound : 범위의 첫 번째 요소를 가리키는 반복기를 반환합니다.

• 값보다 작거나 같음 (내림차순 배열 또는 벡터의 경우)
• 값보다 크거나 같음 (배열 또는 벡터의 오름차순)

std :: upper_bound : 범위의 첫 번째 요소를 가리키는 반복기를 반환합니다.

• 값보다 작음 (내림차순 배열 또는 벡터의 경우)

• 값보다 큼 (배열 또는 벡터의 오름차순)

참조 URL : https://stackoverflow.com/questions/23554509/rationale-for-stdlower-bound-and-stdupper-bound