[CS504주차] Linear Search

순차 탐색 즉, 자료구조를 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 순차적으로 검색한다. 

이런식으로 자료들을 검색할 경우, 원하는 원소가 마지막 인덱스에 저장 되어있다면 처음부터 끝까지 검색을 해야하기 때문에 정확하지만 비효율적인 알고리즘이다. 하지만 자료가 정렬되어있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에는 유용하다.

⁉️시간이 오래 걸리고 공간을 더 많이 차지 하는데 왜 정렬을 해줘야 할까?
여러번 리스트를 검색해야 하거나 매운 큰 리스트를 검색해야 할 경우 시간을 단축시킬 수 있다. 

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

int main(void)
{
    // numbers 배열 정의 및 값 입력
    int numbers[] = {4, 8, 15, 16, 23, 42};

    // 값 50 검색
    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의 배열이 알파벳 순으로 정렬이 된되면 number의 배열을 어떤 방법을 정렬을 해야할지 어려움이 있기 때문에 캡슐화를 시켜준다. 캡슐화는 사용자가 정의할 수 있는 data type을 만들어 이름과 전화번호를 묶어 줄 수 있다. 

 

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

          🔼캡슐화 된 전화번호 프로그램 코드 

 

hahasof.tistory.com/5

순차탐색의 시간복잡도 (Linear Search의 Time Complexity)

www.boostcourse.org/cs112/lecture/119021/

모두를 위한 컴퓨터 과학 (CS50 2019)