본문 바로가기

컴퓨터 공학/알고리즘

[탐색 알고리즘] 순차 탐색 알고리즘(Linear Search)


[탐색 알고리즘] 순차 탐색 알고리즘(Linear Search)


순차 탐색 알고리즘

맨앞에서 부터 맨끝까지 순서대로 탐색을 진행하는 알고리즘.

시간 복잡도 O(n)을 가진다.(Worst Case)


종료 조건

배열의 길이 내에서 숫자 발견시 종료. 탐색 실패시 배열의 길이만큼 탐색 후 종료된다.


Code

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
31
32
#include <stdio.h>
 
// 순차 탐색 알고리즘 함수
// 찾는 숫자가 있으면 찾는 숫자의 인덱스 리턴
// 없으면 -1 리턴
int LSearch(int ar[], int len, int target){
    int i = 0;
    for (; i < len; i++){
        if (ar[i] == target){
            return i;
        }
    }
    return -1;
}
 
int main(int arc, char** argv){
    int arr[] = { 318567294 };
    int idx = 0, inputNum = 0;
 
    // 찾는 숫자 입력
    scanf_s("%d", &inputNum);
    idx = LSearch(arr, sizeof(arr) / sizeof(int), inputNum);
 
    if (idx == -1){
        printf("Fail!!\n");
    }
    else{
        printf("Target Index : %d\n", idx);
    }
 
    return 0;
}
cs


Output

1
2
3
4
5
6
7
8
9
10
11
Case 1
 
input : 10
Fail!!
 
-----------------
 
Case 2
 
input : 5
Target Index : 3
cs