이진 검색

이진 검색은 정렬된 시퀀스에서만 사용할 수 있지만, 시간 복잡도는 선형 검색보다 효율적입니다.

이진 검색의 알고리즘은 다음과 같습니다.

1. 시퀀스의 범위를 측정합니다.
2. 시퀀스의 가운데 원소와 찾고자 하는 값을 비교합니다. (만일 두 원소가 같다면 true를 반환)
3. 가운데 원소와 찾고자 하는 값을 비교하여
   • 가운데 원소보다 값이 작다면, 가운데 원소부터 그 이상의 원소를 제거합니다.
   • 반대로 작다면, 가운데 원소부터 그 이하의 원소를 제거합니다.
4. 범위를 다시 측정하여 측정한 범위가 1 초과이면 2 번쨰 과정을 반복합니다.(만일 이 과정을 수행할 수 없다면, 시퀀스에는 찾고자 한 원소가 존재하지 않는 것이기에 false를 반환합니다.)
   

다음은 이진 검색의 C++ 코드입니다.

bool binary_search(int N, vector<int>& S)
{
    auto first = S.begin();
    auto last = S.end();
 
    while(true)
    {
        auto lenth = distance(first, last);
        auto middle_index = first+floor(lenth/2);
        auto middle = *(middle_index);
 
        if(middle==N)
            return true;
        if(middle>N)
            advance(last, middle_index);
        else
            advance(first, middle_index);
        
        if(lenth==1)
            return false;
    }
}

이제 두 가지 경우의 소모 시간을 비교해보겠습니다.

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
using namespace std;
 
bool linear_search(int N, vector<int>& S)
{
    for(auto i : S)
    {
        if(i==N)
            return true;
    }
    return false;
}
 
bool binary_search(int N, vector<int>& S)
{
    auto first = S.begin();
    auto last = S.end();
 
    while(true)
    {
        auto range_length = distance(first, last);
        auto middle_index = range_length / 2;
        auto middle = *(first + middle_index);
 
        if(middle == N)
            return true;
        else if(middle > N)
            advance(last, -middle_index);
        if(middle < N)
            advance(first, middle_index);
 
        if(range_length == 1)
            return false;
    }
}
 
 
void search_test(int size, int N)
{
    vector<int> S;
    random_device rd;
    mt19937 rand(rd());
 
    uniform_int_distribution<mt19937::result_type> uniform_dist(1,size);
 
    for(auto i =0; i<size;i++)
        S.push_back(uniform_dist(rand));
 
    sort(S.begin(),S.end());
 
    chrono::steady_clock::time_point begin = chrono::steady_clock::now();
    bool search_result=binary_search(N,S);
    chrono::steady_clock::time_point end = chrono::steady_clock::now();
    auto diff = std::chrono::duration_cast<chrono::microseconds>(end-begin);
    cout<<"이진 검색 수행 시간:"<<diff.count()<<endl;
 
    if(search_result)
        cout<<"이진 검색으로 원소를 찾았습니다."<<endl;
    else
        cout<<"이진 검색으로 원소를 찾지 못했습니다."<<endl;
 
    chrono::steady_clock::time_point begin1 = chrono::steady_clock::now();
    bool search_result1=linear_search(N,S);
    chrono::steady_clock::time_point end1 = chrono::steady_clock::now();
    auto diff1 = chrono::duration_cast<chrono::microseconds>(end1-begin1);
    cout<<"선형 검색 수행 시간:"<<diff1.count()<<endl;
 
    if(search_result1)
        cout<<"선형 검색으로 원소를 찾았습니다."<<endl;
    else
        cout<<"선형 검색으로 원소를 찾지 못했습니다."<<endl;
    cout<<"-----------------------------------------"<<endl;
}
 
int main()
{
    search_test(100000, 36543);
    search_test(1000000, 36543);
    search_test(10000000, 36543);
    
    return 0;
}

이진 검색의 수행시간은 0에 수렴하지만, 선형 검색의 경우 범위가 늘어남에 따라서 시간도 비례해서 늘어나는 모습을 볼 수 있다.

sort
C++ 표준 라이브러리에서 제공하는 정렬 알고리즘이며, 임의 접근 반복자의 범위내의 요소들을 정렬합니다. 기본적으로는 올림차순이나 원한다면 내림차순도 가능합니다.

함수의 기본형은 다음과 같습니다.

template<class RandomIt>
void sort(RandomIt first, RandomIt last);
 
template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

여기서 comp는 비교함수이고, 그 값에 따라 오름차순과 내림차순으로 나눠집니다. 간단한 예제를 보겠습니다.

std::sort(numbers.begin(), numbers.end(), [](int a, int b) {return a > b;});

이 경우 비교함수의 첫 번째 인자가 두 번째 인자보다 크기에 sort함수의 3번째 전달인자 값이 true가 되어 내림차순이 됩니다. 하지만 직접적으로 true 값을 전달인자 값으로 주어서는 안됩니다.

#include <chrono>
이 헤더파일은 시간을 다루기 위해 사용하는 헤더파일입니다. 포함되어 있는 클래스는 다음과 같습니다.

chrono::duration
chrono::time_point
chrono::system_clock
chrono::high_resolution_clock
chrono::steady_clock

1. chrono::duration는 주로 chrono::duration<Rep, Period>형식으로 사용되며
   Rep은 자료형, Period는 시간의 간격의 단위를 나타낸다.
   

2. chrono::time_point는 특정 시간을 나타냅니다. 주로 chrono::time_point<Clock, Duration>형태로 사용하며
   Clock은 측정하는 시계의 자료형을, Duration는 시각을 나타내는 시계의 자료형을 나타냅니다.

3. chrono::system_clock는 현제 시간을 내타내며, 다음처럼 사용합니다. chrono::time_point<chrono::system_clock>

4. chrono::high_resolution_clock는 고해상도의 시간을 측정하는데 사용되며, 다음과 같이 사용합니다. chrono::time_point<chrono::high_resolution_clock>

5. std::chrono::steady_clock는 위의 클래스가 고해상도라면, 이 친구는 안정적인 속성을 지닌 시계이며 다음과 같이 사용합니다. chrono::time_point<chrono::steady_clock>

#include <random>

이 헤더파일은 난수를 생성하기 위해 사용되는 헤더파일이며, 포함된 클래스는 다음과 같습니다.

random_device
default_random_engine
uniform_int_distribution
uniform_real_distribution
normal_distribution
bernoulli_distribution
mt19937 rand(rd())

1. random_device는 하드웨어 기반의 난수 생성 장치에 접근할 수 있는 인터페이스를 제공하는 클래스입니다.
   반환형은 random_device::result_type이고, result_type은 일반적으로 부호가 없는 정수 타입입니다.
2. default_random_engine는 난수 생성을 담당하는 클래스입니다
   반환형은 일반적으로 부호가 없는 정수 입니다.
3. uniform_int_distribution는 균일 분포에서 정수를 생성하는데 사용됩니다.
   반환형은 템플릿에 따라 다르지만 일반적으로 정수입니다.
4. uniform_real_distribution는 균일 분포에서 실수를 생성하는데 사용됩니다.
   반환형은 템플릿에 따라 다르지만 일반적으로 실수입니다.
5. normal_distribution는 정규 분포에서 난수를 생성하는데 사용됩니다.
   반환형은 템플릿에 따라 다르지만 일반적으로 생성된 난수입니다.
6. bernoulli_distribution는 베르누이 분포에서 난수를 생성하는데 사용됩니다.
   반환형은 템플릿에 따라 다르지만 일반적으로 bool입니다.
7. mt19937 rand(rd())은 Mersenne Twister 알고리즘을 구현한 난수 생성 엔진 중 하나입니다. C에서의 srand과 유사하다고 생각하면 되겠습니다.

#include <algorithm>
이 헤더파일은 4장에서 다시 볼 것이기에 간단히만 알아보도록 하겠습니다.

정렬 알고리즘	(Sorting Algorithm)
sort	범위의 요소들을 정렬합니다.
partial_sort	범위를 정렬하지만 정렬된 일부만 유지합니다.
nth_element	특정 순서의 요소를 찾습니다.
부가설명	퀵 정렬처럼 정렬후의 인덱스를 찾는 것이 아닌 정렬되지 않은 상태에서의 원소값을 반환합니다.
이진 검색 알고리즘	(Binary Search Algorithms)
binary_search	이진 검색을 수행하여 요소의 존재 여부를 확인합니다.
lower_bound	이진 검색을 사용하여 특정 값 이상의 첫 번째 위치를 찾습니다.
부가설명	{1, 2, 4, 4, 6, 7}배열에서 lower_bound(4)를 사용하면 4가 처음으로 나온 2번 인덱스의 주소를 반환합니다.
upper_bound	이진 검색을 사용하여 특정 값보다 큰 첫 번째 위치를 찾습니다.
부가설명	{1, 2, 4, 4, 6, 7}배열에서 upper_bound(4)를 사용하면, 4라는 원소값의 다음값인 6의 주소를 반환합니다.
비교 알고리즘	(Comparison Algorithms)
equal	두 범위가 동일한지 확인합니다.
lexicographical_compare	두 범위를 사전식으로 비교합니다.
부가 설명	사전식은 인덱스를 의미하며, 0번 인덱스부터 순차대로 비교하여 차이가 발생했을시 큰지 작은지 같은지에 따라 bool값을 반환합니다.
순열과 조합	(Permutations and Combinations)
next_permutation	다음 순열을 생성합니다.
prev_permutation	이전 순열을 생성합니다.
부가설명	순열이란 {1,2,3},{1,3,2}등등 원소값은 같으니 그 순서가 다른 값들을 순열이라 하는데 여기서 순열의 순서는 첫 인덱스가 다음 인덱스가 작은 순으로 나열됩니다.
rotate	요소들을 회전시킵니다.
부가설명	전달인자로 설정할 범위의 시작위치와 끝 위치를 받고, 선택된 정렬이 배열의 어느 부분까지 움직일지에 대해서 3번째 전달인자를 받습니다.
그 외의 알고리즘들
max, min	두 값 중 큰 값 또는 작은 값을 반환합니다.
max_element, min_element	범위에서 최댓값 또는 최솟값의 위치를 찾습니다.
copy	요소를 다른 범위로 복사합니다.
reverse	범위의 요소들을 뒤집습니다.
partition_copy()	분할 연산을 수행하고, 두 배열을 반환한다.
부가설명	반환될 반환값이 두개이기에 pair을 통해 받거나 람다함수를 통하여 다음과 같이도 사용할 수 있습니다.

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> source = {1, 2, 3, 4, 5, 6};
    std::vector<int> true_values;
    std::vector<int> false_values;
 
    auto partition_result = std::partition_copy(
        source.begin(), source.end(),
        std::back_inserter(true_values),
        std::back_inserter(false_values),
        [](int x) { return x % 2 == 0; }
    );
    return 0;
}

이 결과 반환된 값은 다음과 같을 것 입니다.
true_values: {2, 4, 6}, false_values: {1, 3, 5}