[algo] binary search 정리

참고 링크: 바킹독의 실전 알고리즘_0x13 이분탐색

---

이분탐색

• 전제 : 정렬되어 있는 배열
• 탐색 범위를 절반으로 줄여가며 찾는 search
• $O(log N)$
• 무한 루프에 빠지지 않게 mid 값 정해야 됨

STL

std::binary_search

이분탐색 STL

• 헤더 : <algorithm>
• 반환값 (Return): 원소를 찾으면 true, 찾지 못하면 false를 반환하는 bool 타입
• $O(log N)$
• 미리 정렬되어 있어야 됨

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);


// example
bool found30 = binary_search(v.begin(), v.end(), 30);

std::lower/upper_bound

• 헤더 : <algorithm>
• 반환값 (Return): 지정된 값 이상(lower_bound) 혹은 초과(upper_bound)하는 값이 처음으로 나타나는 위치의 iterator 을 return.
• $O(log N)$ : 이진 탐색 기반임
• 미리 정렬되어 있어야 됨

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 이미 오름차순 정렬된 벡터 (20이 3개 중복되어 있음)
    vector<int> v = {10, 20, 20, 20, 30, 40};

    // 1. lower_bound: 20 "이상"이 처음 나오는 위치
    auto lower = lower_bound(v.begin(), v.end(), 20);
    
    // 2. upper_bound: 20을 "초과"하는 값이 처음 나오는 위치
    auto upper = upper_bound(v.begin(), v.end(), 20);

    // 3. 인덱스 구하기 (반복자에서 v.begin()을 뺌)
    int lower_index = lower - v.begin();
    int upper_index = upper - v.begin();

    return 0;
}

---

parametric search

조건을 만족하는 최소/최댓값을 구하는 문제, 즉 최적화 문제를 결정 문제로 변환해 이분탐색을 수행하는 방법

ex. 랜선 자르기 문제

• 최적화 문제 : N개를 만들 수 있는 랜선의 최대 길이 찾기
• 결정 문제 : 랜선의 길이가 X일 때 랜선이 N개 이상인가 아닌가