[C++] 선형 탐색(Linear Search), 이진 탐색(Binary Search)

선형 탐색(Linear Search), 이진 탐색(Binary Search)

선형 탐색(Linear Search)

• 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인
• 다음과 같은 코드로 구현할 수 있음.

bool linear_search(int N, std::vector<int>& sequence) {
    for (auto i : sequence) {
        if (i == N) {
            return true;    // 찾음!
        }
    }
    return false;
}

• 장점
  • 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작함.
• 단점
  • 효율적이지 않음.
  • 주어진 배열이 정렬되어 있다는 점을 전혀 이용하지 못함.
• 시간 복잡도 : O(N)

 

이진 탐색(Binary Search)

• 주어진 시퀀스가 정렬되어 있다는 사실을 이용하여 검색하는 방법
• 검색 방법 (찾고자 하는 원소 : N)
  • ① 전체 시퀀스 범위를 range로 설정
  • ② 현재 range의 가운데 원소를 M이라고 하고, M과 N을 비교
    • M = N
      • 시퀀스에서 N을 찾은 것이므로 검색을 중단함.
    • M ≠ N
      • 다음의 두 규칙에 따라 range 수정
        • N < M
          • N은 M의 왼쪽에 있을 것으로 예상할 수 있음.
          • range에서 M 오른쪽에 있는 모든 원소는 제거함.
        • N > M
          • N은 M의 오른쪽에 있을 것으로 예상할 수 있음.
          • range에서 M 왼쪽에 있는 모든 원소는 제거함.
  • ③ 만약 range에 1개 보다 많은 원소가 남아 있다면 ②로 이동함.
    • 그렇지 않으면 주어진 시퀀스에 N이 존재하지 않는 것이며, 검색을 종료함.

 

예) 1부터 9까지의 정수가 차례대로 증가하는 시퀀스 S에서 N = 2를 찾는 이진 탐색

1단계

• S의 모든 원소를 range로 간주함.
• 현재 range에서 가운데 원소는 5
• 그러므로 N과 5를 비교함.

 

2단계

• N < 5이므로, N이 시퀀스에 있다면 5 왼쪽에 있을 것임.
• 그러므로 입력 시퀀스에서 원소 5 보다 오른쪽에 있는 원소들은 검색에서 고려하지 않아도 됨.
• 이제 검색 범위 range를 1에서 5 사이로 설정함.
  • 가운데 원소가 3이 됨.
    • N과 3을 비교함.

 

3단계

• N < 3이므로, 시퀀스 시작위치부터 원소 3이 있는 위치까지를 새로운 range로 설정함.
  • 가운데 원소가 2가 됨.
    • N = 2이므로 검색을 종료함.

 

코드

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>

bool linear_search(int N, std::vector<int>& S) {
    for (auto i : S) {
        if (i == N) {
            return true;    // 원소 찾음!
        }
    }
    return false;
}

bool binary_search(int N, std::vector<int>& S) {
    auto first = S.begin();
    auto last = S.end();

    while (true) {
        // 현재 검색 범위의 중간 원소를 mid_element에 저장
        auto range_length = std::distance(first, last);
        auto mid_element_index = std::floor(range_length / 2);
        auto mid_element = *(first + mid_element_index);

        // mid_element와 N 값을 비교
        if (mid_element == N) {
            return true;
        }
        else if (mid_element > N) {
            std::advance(last, -mid_element_index);   // 현재 iterator의 시작 위치(last)를 last + -last-mid_element_index 로 이동함.
        }
        else {
            std::advance(first, mid_element_index);   // 현재 iterator의 시작 위치(first)를 first + mid_element_index 로 이동함.
        }

        // 현재 검색 범위에 하나의 원소만 남아 있다면 false 반환
        if (range_length == 1) {
            return false;
        }
    }
}

void run_small_search_test() {
    auto N = 2;
    std::vector<int> S {1, 3, 2, 4, 5, 7, 9, 8, 6};

    std::sort(S.begin(), S.end());

    if (linear_search(N, S)) {
        std::cout << "선형 검색으로 원소를 찾았습니다!" << std::endl;
    }
    else {
        std::cout << "선형 검색으로 원소를 찾지 못했습니다." << std::endl;
    }

    if (binary_search(N, S)) {
        std::cout << "이진 검색으로 원소를 찾았습니다!" << std::endl;
    }
    else {
        std::cout << "이진 검색으로 원소를 찾지 못했습니다." << std::endl;
    }
}

void run_large_search_test(int size, int N) {
    std::vector<int> S;
    std::random_device rd;
    std::mt19937 rand(rd());

    // [1, size] 범위에서 정수 난수 발생
    std::uniform_int_distribution<std::mt19937::result_type> uniform_dist(1, size);

    // S에 난수 추가
    for (auto i = 0; i < size; i++) {
        S.push_back(uniform_dist(rand));
    }

    std::sort(S.begin(), S.end());

    // 검색 시간 측정 시작
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

    bool search_result = binary_search(N, S);

    // 검색 시간 측정 종료
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

    auto diff = std::chrono::duration_cast<std::chrono::microseconds>(end - begin);
    std::cout << "이진 탐색 수행 시간: " << diff.count() << std::endl;

    if (search_result) {
        std::cout << "원소를 찾았습니다." << std::endl;
    }
    else {
        std::cout << "원소를 찾지 못했습니다." << std::endl;
    }
}

int main() {
    run_small_search_test();

    run_large_search_test(100000, 36543);
    run_large_search_test(1000000, 36543);
    run_large_search_test(10000000, 36543);

    return 0;
}

 

결과

선형 검색으로 원소를 찾았습니다!
이진 검색으로 원소를 찾았습니다!
이진 탐색 수행 시간: 1
원소를 찾았습니다.
이진 탐색 수행 시간: 2
원소를 찾지 못했습니다.
이진 탐색 수행 시간: 2
원소를 찾지 못했습니다.