자료구조 - 순차 탐색

[순차 탐색(Sequential Search)]

순차 탐색(Sequential Search)은 가장 기본적인 탐색 알고리즘 중 하나로, 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색하여 원하는 값을 찾는 방법입니다.

리스트가 정렬되어 있지 않은 경우에도 사용할 수 있으며, 구현이 매우 간단합니다.

 

 

순차 탐색 작동 원리

1. 리스트의 첫 번째 요소부터 시작하여 하나씩 확인합니다.
2. 현재 요소가 찾고자 하는 값과 일치하면, 해당 요소의 인덱스를 반환합니다.
3. 끝까지 탐색했는데도 찾고자 하는 값을 발견하지 못하면, 값이 리스트에 없다는 뜻이므로 -1을 반환합니다.

 

순차 탐색 의사 코드

함수 sequentialSearch(arr, key):
    for i = 0부터 arr의 길이까지:
        if arr[i] == key:
            반환 i // key의 인덱스 반환
    반환 -1 // key를 찾을 수 없는 경우

 

 

순차 탐색 예제

예제 리스트: [64, 25, 12, 22, 11]
찾고자 하는 값: 22

1. 리스트의 첫 번째 요소 64와 22를 비교합니다. 일치하지 않으므로 다음 요소로 이동합니다.

2. 두 번째 요소 25와 22를 비교합니다. 일치하지 않으므로 다음 요소로 이동합니다.

3. 세 번째 요소 12와 22를 비교합니다. 일치하지 않으므로 다음 요소로 이동합니다.

4. 네 번째 요소 22와 22를 비교합니다. 일치하므로 해당 요소의 인덱스 3을 반환합니다.

 

 

순차 탐색 코드

#include <iostream>
#include <vector>

using namespace std;

// 순차 탐색 함수
// arr: 탐색할 배열, key: 찾고자 하는 값
int sequentialSearch(const vector<int>& arr, int key) 
{
    // 배열의 모든 요소를 순차적으로 탐색
    for (int i = 0; i < arr.size(); i++) 
    {
        // 현재 요소가 찾고자 하는 값과 같으면 인덱스를 반환
        if (arr[i] == key) 
        {
            return i;
        }
    }
    // 찾고자 하는 값을 배열에서 찾지 못하면 -1 반환
    return -1;
}

int main()
{
    vector<int> arr = {64, 25, 12, 22, 11}; // 예제 배열
    int key = 22; // 찾고자 하는 값

    // 순차 탐색 수행
    int result = sequentialSearch(arr, key);

    // 결과 출력
    if (result != -1) 
    {
        cout << "값 " << key << "을(를) 인덱스 " << result << "에서 찾았습니다." << endl;
    } 
    else 
    {
        cout << "값 " << key << "을(를) 배열에서 찾을 수 없습니다." << endl;
    }

    return 0;
}

 

 

 

순차 탐색의 장단점

 

장점 :

1. 간단한 구현: 알고리즘이 단순하여 구현하기 쉽습니다.
2. 정렬 불필요: 데이터가 정렬되어 있지 않아도 사용할 수 있습니다.
3. 작은 데이터에 효율적: 데이터의 크기가 작을 때는 효율적입니다.

 

단점 :

1. 비효율성: 데이터의 크기가 커질수록 탐색 시간이 길어져 비효율적입니다.
2. 최악의 경우: 최악의 경우 모든 요소를 탐색해야 합니다.

 

 

시간 복잡도

 

• 최선의 경우: O(1)O(1)O(1) (찾고자 하는 값이 배열의 첫 번째 요소일 때)
• 최악의 경우: O(n)O(n)O(n) (찾고자 하는 값이 배열의 마지막 요소일 때 또는 배열에 없을 때)
• 평균의 경우: O(n)O(n)O(n)