[Algorithms] 501. 순차 검색

순차 검색 (Linear Search)

순차 검색은 가장 기본적인 검색 방법입니다.
검색 대상이 되는 데이터를 순서대로 조회하면서 조건에 부합하는 데이터를 찾아냅니다.

#include <iostream>
#include <string>
#include <vector>

struct Data
{
    std::string name;
    int age;
};

class DataSet
{
private:
    std::vector dataVec;
public:
    void AddData(std::string name, int age)
    {
        Data newData;
        newData.name = name;
        newData.age = age;

        dataVec.push_back(newData);
    }

    Data LinearSearch(std::string name)
    {
        for (Data& ref : dataVec)
        {
            if (ref.name.compare(name) == 0)
            {
                return ref;
            }
        }
        return Data();
    }
};

int main(int argc, char** argv)
{
    DataSet dataSet;

    dataSet.AddData("Tom", 32);
    dataSet.AddData("John", 20);
    dataSet.AddData("Alex", 17);

    std::cout << dataSet.LinearSearch("John").age << std::endl;
}

간단한 for반복문을 사용한 순차검색의 예제 코드입니다.
vector에 포함된 데이터를 순회하면서 검색 대상을 찾아냅니다.

순차검색에서 검색대상이 발견되었을 때의 동작은 크게 두가지로 나눠볼 수 있습니다.
하나는 그 즉시 발견된 검색값을 되돌려 주는 방법이며,
다른 하나는 남아있는 모든 데이터에 대해 검색을 계속하여 한번에 데이터 집합을 되돌려 주는 방법입니다.

순차검색은 최악의 경우 검색 대상 전체인 N개의 값을 검사해야 하며, 그다지 빠른 검색방법은 아닙니다.
하지만 다른 검색 알고리즘과는 다르게 코드로 옮겼을 때 간단하고,
별다른 중간 계산비용이 들어가지 않는다는 장점이 있으며,
때때로 자료구조 설계에 따라 순차검색만이 가능한 경우도 있습니다.