C++ binary search 관련

binary_search() 함수

안에 내용이 있는지 없는지만 bool형으로 알려줌

실행전에 정렬되어 있어야 함 

vector<int> v{3,2,1,4,6};
sort(v.begin(), v.end());
binary_search(v.begin(), v.end(), 3); // true

int comp(int a, int b) {return a-b;}

binary_search(v.begin(), v.end(), 5, comp); // false

 

equal_range() 함수

이진 탐색을 이용하며, 해당 값이 어디부터 어디까지 있는지 알려줌

마찬가지로 정렬되어 있어야 함

vector<int> v{6,3,2,10,10,10,-10,-10,7,3,20};
pair<vector<int>::iterator, vector<int>::iterator> bounds;

sort(v.begin(), v.end()); // {-10, -10, 2, 3, 3, 6, 7, 10, 10, 10, 20}
bounds = equal_range(v.begin(), v.end(), 10); //       ^           ^ 
cout << distance(v.begin(), bounds.first); // 7
cout << distance(v.begin(), bounds.second); // 10

 

lower_bound() 함수

value 이상의 처음 나오는 위치

vector<int> v{1,2,4,5,6,6,7,7,7,9};
//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 6); //            ^

//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 7); //                  ^

//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 8); //                           ^

//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 9); //                           ^

 

upper_bound() 함수

value 초과의 처음 나오는 위치

vector<int> v{1,2,4,5,6,6,7,7,7,9};
//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 6); //                  ^

//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 7); //                           ^

//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 8); //                           ^

//                                    1, 2, 4, 5, 6, 6, 7, 7, 7, 9
lower_bound(v.begin(), v.end(), 9); //                              ^