이진 탐색(Binary Search)

목표

이진 탐색 정의 설명

과정 설명

구현

시간복잡도와 공간복잡도 계산

정의

순차탐색과 다르게 특정 원소의 존재 여부를 파악하는데에 O(logn) 시간에 해결하는 알고리즘이다.

과정

1. 배열의 중앙값을 찾는다.

2. 중앙값보다 크면 오른쪽 부분 배열을 탐색하고 작으면 왼쪽 부분 배열을 탐색한다.

3. 이 과정을 반복하면서 값을 찾고 start가 end보다 커지면 값을 찾지 못한 것이다.

구현

1. 전통적인 이진 탐색 구현 방법

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100000];
void search(int num, int start, int end)
{
    int middle = (start+end)/2;
    while(start <= end)
    {
        if(arr[middle] == num)
        {
            cout << "find" << '\n';
            return;
        }
        if(num > arr[middle])
            start = middle + 1;
        else
            end = middle - 1;
        middle = (start + end) / 2;
    }
    cout << "not find" << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    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++)
    {
        int num;
        cin >> num;
        search(num, 0, n);
    }
    return 0;
}

2. 왼쪽에서 오른쪽으로 건너 뛰면서 확인하는 방법 - 특정 함수를 사용하여 최적해를 구할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100000];
int n, m;
void search(int num, int start, int end)
{
    int k = 0;
    for(int i = n/2; i>=1; i/=2)
    {
        while(arr[i+k] <= num && i+k < n) k += i;
        

    }
    if(arr[k] == num)
        cout << "find" << '\n';
    else
        cout << "not found" << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    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++)
    {
        int num;
        cin >> num;
        search(num, 0, n);
    }
    return 0;
}

보통 이진 탐색만 단독으로 사용되기 보다는 최적해를 구하는 문제에서 사용되므로 아래 코드도 같이 보는 것이 좋다.

시간복잡도와 공간복잡도

시간복잡도: 이진 탐색은 반드시 정렬되어 있다는 가정 하에 사용되기 때문에 배열의 크기가 8이라고 할 때 배열을 3번 나눌 수 있다. 3 = log8 따라서 O(logn)이다.

공간복잡도: 추가적인 배열을 사용하지 않고 n 크기의 배열을 그대로 사용하기에 O(n)이다.

 

이진탐색은 반드시 정렬되어 있어야 하며 이진 탐색을 사용하여 최적해를 찾는 경우  최적해를 가질 수 없는 구간의 최댓값을 이진탐색으로 알아내는 것이다. 그후 해당 값보다 + 1 할 경우 무조건 최적해를 갖기에  최적해의 최솟값이 된다.