[알고리즘] 선형 탐색 (Linear Search)

선형 탐색 개념

선형 탐색이란 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하는 알고리즘이다.

검색이 종료되는 종료 조건
1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

찾는 대상이 앞쪽에 있으면 짧은 시간에 탐색할 수 있지만 뒤쪽에 있거나 결과가 없거나 혹은 탐색대상이 많으면 많은 시간이 걸리고 비효율적일 수 있다.

선형탐색의 장단점

장점

• 맨 앞에서 순서대로 하나씩 탐색해 나가기 때문에 구현이 매우 간단하다.

단점

• 데이터 수가 많아지면 찾아내는 시간이 많이 소요되어 효율이 좋지 않다.

시간복잡도

$O(n)$

구현

#include <iostream>
#include <vector>

using namespace std;

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

int main(){
    vector<int> vec = {1, 2, 3, 4, 5};
    //vector에 값이 존재하면 1, 존재하지 않으면 0 출력
    cout << linear_search(3, vec) << endl;
    cout << linear_search(7, vec) << endl;
}

보초법

선형 검색은 반복할 때마다 검색 종료조건 1과 2를 모두 반복한다.
이 비용을 반으로 줄이는 방법이 보초법(sentinel method)이다. 검색하고자 하는 key 값을 배열의 맨끝 요소에 저장한다. 이 때 저장하는 값을 보초라고 한다.
보초법을 실행할 경우 위의 종료 조건 중 2번만 만족시키면 되기 때문에 반복 종료에 대한 판단 횟수는 절반으로 줄어들게 된다.