[알고리즘] 선형 검색

선형  검색

선형 검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.

찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 한다.

자료를 검색하는 데 사용되는 알고리즘 중 하나이다.

 

효율성 그리고 비효율성

선형 검색 알고리즘은 정확하다. 하지만 효율적이지 못하다.

예를 들어 만약 100만 개의 원소가 있는 리스트라고 가정한다면..

찾고자 하는 원소가 가장 마지막에 담겨있다면..굉장히 오랜시간을 탐색해야 할것이다.

 

하지만 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.

 

 

#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";

    // EMMA 검색
    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 이라는 구조체를 자료형으로 정의하여 

각각의 전화번호 이름을 저장한 후, 

선형 검색을 활용하여 해당 사람의 번호를 찾는  전화번호부 프로그램이다.