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

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

순차 탐색 알고리즘

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

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

종료 조건

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

Code

#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[] = { 3, 1, 8, 5, 6, 7, 2, 9, 4 };
    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;
}

Output

Case 1
 
input : 10
Fail!!
 
-----------------
 
Case 2
 
input : 5
Target Index : 3