[41] - Binary Search

Sorting을 진행한 컨테이너에 대해서 실시할 수 있는 몇 가지 Algorithm들이 존재합니다. 그 중에 하나가 Binary Search이며 merge, include 등등의 operation도 수행할 수 있습니다.

몇 가지 함수들이 존재합니다. 한 가지 주의해야 할 점은 이 std::binary_search는 찾는 요소의 iterator를 반환하는 것이 아니라 Boolean을 반환하는 함수로써 컨테이너 내부에 격납 여부만 판단해 줄 수 있다는 점입니다.

Boolean을 반환합니다

대신에 std:lower_bound와 std::upper_bound라는 함수가 존재합니다. 이들이 iterator를 반환합니다. 대신에 원하는 값을 반환하는 것이 아니라 그것 작지는 않으면서 전체집합 중에서는 가장 작은 요소의 Iterator를 반환합니다. 가령 다음과 같은 수가 있을 때, 16을 찾는다면 18을 내놓을 것입니다.

{ 1,2,3,4,5,6,14,18,20 } -> 16보다 작지 않은 18을 대신 내놓을 것.

std::find와 std::equal_range의 차이는 역시 퍼포먼스에 있습니다. std::equal_range가 성능 면에서 낫습니다.

별로 볼 것이 없습니다.