이진 탐색(Binary Search)

• 정렬된 배열 또는 리스트에서 특정 원소를 찾기 위해 사용

• 주어진 값과 배열의 중간 값과의 비교를 통해 검색 범위를 반으로 줄여가면서 원소를 찾음

  • 1. 중간 원소 찾기
  • 2. 중간 원소와 찾고자 하는 값 비교
    • 중간 원소와 찾고자 하는 값이 일치하면 원하는 원소를 찾은 것
    • 일치하지 않으면 찾고자 하는 값이 중간 원소의 왼쪽 또는 오른쪽에 있음 -> 검색 범위를 중간 원소의 왼쪽 또는 오른쪽으로 조정하여 반복

• 시간 복잡도가 O(log n)

• 배열 또는 리스트가 정렬되어 있어야 하므로, 삽입, 삭제 등의 연산이 빈번하게 일어나는 동적인 자료구조에는 적용하기 어려움

• algorithm에 정의된 binary_search 함수

template <class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);

• 직접 구현할 경우 다음과 같은 반복문 또는 재귀로 작성 가능

bool binary_search_custom(int arr[], int len, int key)
{
	int start = 0;
	int end = len-1;
    int mid;
    while(end - start >= 0)
    {
    	mid = (start + end) / 2;  //중앙 값
        if (arr[mid] == key)  // key 값을 찾았을 때
        {
        	return true;
        }
        else if (arr[mid] > key)  // 중앙값이 key 값보다 작을 때 = key값이 중앙값의 왼쪽에 있을 때
        {
        	end = mid - 1;
        }
        else  // key값이 중앙값보다 클 때 = key값이 중앙값의 오른쪽에 있을 때
        {
        	start = mid + 1;
        }
    }

	return false;
}

전체 코드

1) binary_search 직접 구현

#include <iostream>
#include <algorithm>

using namespace std;

bool binary_search_custom(int arr[], int len, int key)
{
	int start = 0;
	int end = len-1;
    int mid;
    while(end - start >= 0)
    {
    	mid = (start + end) / 2;  //중앙 값
        if (arr[mid] == key)  // key 값을 찾았을 때
        {
        	return true;
        }
        else if (arr[mid] > key)  // 중앙값이 key 값보다 작을 때 = key값이 중앙값의 왼쪽에 있을 때
        {
        	end = mid - 1;
        }
        else  // key값이 중앙값보다 클 때 = key값이 중앙값의 오른쪽에 있을 때
        {
        	start = mid + 1;
        }
    }

	return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int arr[100001];

    int n, m, num;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr, arr+n);

    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> num;
        if (binary_search_custom(arr, n, num)) {
            cout << "1" << "\n";
        } else {
            cout << "0" << "\n";
        }
    }

    return 0;
}

2) algorithm 헤더파일의 binary_search 함수 사용

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int arr[100001];

    int n, m, num;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr, arr+n);

    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> num;
        if (binary_search(arr, arr+n, num)) {
            cout << "1" << "\n";
        } else {
            cout << "0" << "\n";
        }
    }

    return 0;
}