[CS50] 알고리즘 - 선형 검색

선형 검색(Linear Search)은 원하는 값을 찾을 때까지 처음부터 마지막까지 차례대로 검색하는 방법이다.
찾고자 하는 값이 발견될 때까지 모든 자료를 순서대로 확인한다.

 

효율성

선형 검색은 정확하지만 효율적이지 못한 방법이다.

최악의 경우

• 찾는 값이 맨 마지막에 있거나 없는 경우
• 길이가 n인 배열에서 n번 실행
• 시간 복잡도: O(n)

최선의 경우

• 첫 번째 시도에서 값을 찾는 경우
• 시간 복잡도: Ω(1)

선형 검색은 자료가 정렬되어 있지 않거나 추가 정보가 없을 때 유용하다. 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적이기 때문이다.

 

정렬 후 검색하면 더 빠르지만, 정렬 자체에 시간이 오래 걸린다는 문제가 있다.

 

구현

숫자 배열 검색

주어진 배열에서 특정 값을 찾는 코드다.

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int numbers[] = {4, 8, 15, 16, 23, 42};

    for (int i = 0; i < 6; i++)
    {
        if (numbers[i] == 50)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

배열 크기만큼 루프를 돌며 인덱스를 차례대로 방문하여 값을 검사한다.

 

문자열 배열 검색

전화번호부에서 이름을 찾아 번호를 출력하는 코드다.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617-555-0100", "617-555-0101", "617-555-0102", "617-555-0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

names 배열에서 검색하여 같은 인덱스의 numbers 배열 값을 출력한다.

 

다만 이 경우 names와 numbers 배열이 항상 같은 인덱스를 유지해야만 유용하다.

 

구조체 활용

구조체를 정의하여 이름과 번호를 하나로 묶으면 더 안전하다.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[4];

    people[0].name = "EMMA";
    people[0].number = "617-555-0100";
    people[1].name = "RODRIGO";
    people[1].number = "617-555-0101";
    people[2].name = "BRIAN";
    people[2].number = "617-555-0102";
    people[3].name = "DAVID";
    people[3].number = "617-555-0103";

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(people[i].name, "EMMA") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

 

person 구조체를 자료형으로 정의하고 배열을 선언한다. 속성값은 .으로 접근한다.
person a 변수가 있다면 a.name, a.number로 각각의 값에 접근할 수 있다.