이분탐색(Binary search)

- 이분탐색이란?

이분탐색이란 정렬이 되어있는 배열에서 원하는 데이터를 찾기 위해 순서대로 찾아보는 방법 대신에 탐색 범위를 절반으로 줄여나가며 찾는 탐색 방법이다. boj 문제 중에 이분탐색을 요구하는 문제가 있어서 문제를 보면서 이분탐색의 개념을 정리했다.

- boj 1920 수 찾기

https://www.acmicpc.net/problem/1920

예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 en은 14가 있을 수 있는 범위의 처음과 끝 인덱스를 의미한다. mid는 (st+en)/2 이다. A[mid]와 14의 값을 비교하며 st와 en의 값을 계속 바꿔나갈 것이다.

• 만약 A[mid] > 14 이면, 14는 mid와 en 사이에 있음이 자명하고, 그러므로 st = mid+1 이라고 할 수 있다.
• 만약 A[mid] < 14 이면, 14는 st와 mid 사이에 있음이 자명하고, 그러므로 en= mid-1 이라고 할 수 있다.
• 만약 A[mid] = 14 이면, mid 값을 반환한다.

찾고자 하는 값이 A 안에 있다면, 위와 같은 과정을 거쳐서 A[mid] = target 이 된다. 이 때, target이 A 안에 없다면 en < st가 될 것이다. 이렇게 되면 함수를 종료하고 -1을 반환한다.

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

int N;
int M;
int A[100005];

int BinarySearch(int target, int length)
{
    int st = 0;
    int en = length - 1;

    while (st <= en)
    {
        int mid = (st + en) / 2;
        if (A[mid] < target) st = mid + 1;
        else if (A[mid] > target) en = mid - 1;
        else return mid;
    }
    return -1;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A, A + N);
    cin >> M;

    while (M--)
    {
        int target;
        cin >> target;

        if (BinarySearch(target, N) == -1) cout << '0' << '\n';
        else cout << '1' << '\n';
    }
}

- 이분탐색 STL

• binary_search
  • algorithm 헤더 안에 포함되어있다.
  • 오름차순으로 정리되어 있는 배열/벡터에서만 쓸 수 있다.
  • 입력해준 범위 내에 원소가 들어있는지 여부를 true 또는 false의 값으로 반환한다.
  • 시간복잡도는 O(logN)이다.
• lower_bound / upper_bound
  • 공통점
    • algorithm 헤더 안에 포함되어있다.
    • 오름차순으로 정리되어 있는 배열/벡터에서만 쓸 수 있다.
    • 배열을 넘겨줄 경우 포인터를 반환하고, 벡터를 넘겨줄 경우 iterator를 반환한다.
    • 찾고자 하는 값이 없을 경우, 끝 주소나 iterator를 반환한다.
  • 차이점
    • lower_bound : 주어진 값보다 크거나 같은 값 중에서 가장 작은 값의 위치를 반환한다.
    • upper_bound : 주어진 값보다 큰 값 중에서 가장 작은 값의 위치를 반환한다.