11. 이진 검색

이진 검색

빠른 설명

이진 검색은 정렬된 범위에서 답이 있는 위치를 절반씩 줄이며 찾는 알고리즘이다. 값 검색뿐 아니라 “조건을 만족하는 가장 작은 값”을 찾는 최적화 문제에도 자주 쓰인다.

언제 쓰는가

• 배열이 정렬되어 있을 때
• 가능한 답의 범위가 있고, 조건의 참/거짓이 한쪽 방향으로 유지될 때
• lower_bound, upper_bound, bisect를 쓸 수 있을 때

시간복잡도

• $O(\log N)$

참고자료

• CP-Algorithms - Binary Search
• Wikipedia - Binary search algorithm
• cppreference - lower_bound
• Python - bisect

lower_bound, upper_bound

• 이분 탐색(Binary Search) 헷갈리지 않게 구현하기

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
 
int LowerBound(const vector<int>& v, int x) {
    const int n = v.size();
    int lo = -1, hi = n;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (!(v[mid] >= x)) lo = mid;
        else hi = mid;
    }
    return hi;
}
 
int UpperBound(const vector<int>& v, int x) {
    const int n = v.size();
    int lo = -1, hi = n;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (!(v[mid] > x)) lo = mid;
        else hi = mid;
    }
    return hi;
}
 
int main() {
    fastio;
    vector<int> v = { 1, 2, 3, 3, 4 };
    cout << LowerBound(v, 3) << '\n'; // 2
    cout << UpperBound(v, 3) << '\n'; // 4
    cout << UpperBound(v, 3) - LowerBound(v, 3) << '\n'; // 2
}

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {1, 3, 5, 7, 9};
    int target = 7;
 
    int left = 0, right = (int)a.size() - 1;
    bool found = false;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] == target) {
            found = true;
            break;
        } else if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    cout << found << '\n';
}

Python 코드

a = [1, 3, 5, 7, 9]
target = 7
 
left, right = 0, len(a) - 1
found = False
 
while left <= right:
    mid = (left + right) // 2
    if a[mid] == target:
        found = True
        break
    elif a[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
 
print(found)