알고리즘 선형검색(선형탐색)이란?

안녕하세요 선형검색(선형탐색)에 대해 알아보겠습니다

1.선형검색(Linear search) 이란?

배열에서 데이터를 탐색하는 알고리즘입니다. 배열의 앞에서부터 차례대로 확인하면 됩니다.

2.예시

위와같은 배열이 있을 때, 원하는값을 맨 앞부터 차례대로 찾습니다.

예시1)

찾는 값 : 4

1 -> 아님

2 -> 아님

3 -> 아님

4 -> 맞음

예시2)

찾는 값 : 6

1 -> 아님

2 -> 아님

3 -> 아님

4 -> 아님

5 -> 아님

찾는값이 6인 경우, 원하는 값이 없습니다.

선형검색의 종료 조건은 2개임을 알 수 있습니다

조건 1 : 검색한 값을 찾음

조건 2 : 검색한 값을 못찾음

조건1인경우, 검색성공이고 조건2인경우 검색실패입니다.

3.코드

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <stdio.h>    int search(int num[], int target, int length)  {     int i = 0;     while(1)     {         if(length == i)             return -1;         if(num[i] == target)             return i;         i++;     }      } int main(void)  {      int target,idx;     int num[5] = {1,2,3,4,5};          printf("검색할 값 : ");     scanf("%d",&target);          idx = search(num,target,5);          if(idx == -1)         printf("찾는 값이 없습니다. \n");     else         printf("%d는 num[%d]에있습니다. \n",target,num[idx-1]); }

조건1 ( 코드 10번째줄)

조건2 (코드 8번째줄)

4.보초법

선형검색에는 종료조건이 2가지입니다. (조건1,조건2) 근데 선형검색에서 종료 조건을 반으로 줄이는 방법이 있는데 이것을 보초법이라고 합니다.

보초법은 원래데이터의 맨 뒤에, 검색한 값을 넣어두는 것입니다.

조건 1 : 검색한 값을 찾음

조건 2 : 검색한 값을 못찾음

보초법을 사용하면 조건2를 필요하지 않아서, 판단 횟수는 절반으로 줄어듭니다.

5.보초법예시

예시1)

찾는 값 : 3

1 -> 아님

2 -> 아님

3 -> 맞음

1 -> 아님

2 -> 아님

3 -> 아님

4 -> 아님

5 -> 아님

6 -> 보초값이라서 찾는 값이 없다

5.보초법코드

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <stdio.h>    int search(int num[], int target, int length)  {     int i = 0;     num[5] = target; //보초를 추가      while(1)     {         if(num[i]==target)             break;         i++;     }     return i == length ? -1 : i ;      } int main(void)  {      int target,idx;     int num[6] = {1,2,3,4,5};          printf("찾는 값 : ");     scanf("%d",&target);          idx = search(num,target,5);          if(idx == -1)         printf("찾는 값이 없습니다. \n");     else         printf("%d는 num[%d]에있습니다. \n",target,num[idx-1]); }

출력결과는 3번이랑 같습니다.

코드에서 6번째줄을 보면 보초값을 배열의 맨 뒤에 저장합니다

9번째줄에서는 배열의 값과 찾는 값을 차례대로 있나 검색하고 있다면 while문을 종료합니다.

13번째줄에 return i == length ? -1 : i;은

i의 값이 lenght랑 같다면,  검색한 값과 보초값이 같은거라서 찾지못한 것 입니다