Linear Search (순차 탐색)

기본 탐색 알고리즘 중 하나다. 말 그대로 배열 A의 모든 소요들을 차례대로 (왼쪽부터 오른쪽)으로 탐색을 한다. 정렬되지 않아도 된 배열도 탐색 가능하다.

 

 

추가 설명이 필요없어서 바로 비주얼을 아래에 첨부하겠다.

 

 

 

 

의사코드 마저 되게 간단하다. 특별한 메서드는 필요없고 네이브로 구현했다. 

 

  Linear-Search(A, n, T)
    for i = 0 to n - 1 do 
        if A[i] = T then 
            return i
        i = i + 1
    if i = n then 
        return false

 

 

시간 복잡도는 그냥 간단한 O(n)이다 (nested for loop이 없어서). 공간 복잡도도 역시 O(1)이다. 

 

 

 

아래 레포지토리에 순차 탐색 프로그램을 완성하였다. 다른 알고리즘들에 비해 매우 간다나고 짧지만 그래도 참고하기엔 유용할 것 같다. 

 

GitHub - yoonBot/Algorithm-Library: a library of algorithms sorted by their categories.

 

다음 글에는 조금 더 까다로운(?) 이진 탐색 (Binary Search)에 대해 알아보며 순차 탐색과의 차이점을 알아보겠다.