순차검색(Sequence Search)

순차검색(Sequence Search)

---

순차검색(Sequence Search)은 리스트나 배열에서 원하는 값을 찾기 위해 처음부터 배열의 끝까지 순차적으로 검사하는 검색 알고리즘입니다. 순차 검색 알고리즘은 정렬되지 않은 배열에서도 사용할 수 있지만 탐색해야 하는 요소의 개수가 많아질수록 속도가 느려지는 단점이 존재합니다.

 

동작 원리

1. 0번 인덱스 즉 첫 번째 요소부터 마지막 요소까지 찾으려는 값을 한 요소씩 순차적으로 확인합니다.
2. 확인하는 요소가 값을 찾았다면 해당 위치(인덱스)를 반환하고 찾지 못했을 경우 마지막 요소까지 검사합니다.
3. 마지막까지 검색했는데 발견하지 못했으면 -1 같이 사용자가 정의한 값을 반환하여 없음으로 표시합니다.

 

순차 검색 알고리즘의 시간 복잡도

• 최선의 경우(Best Case) : 찾는 요소가 첫 번째에 있는 경우 에는 O(1)
• 최악의 경우(Worst Case) : 찾는 요소가 마지막에 위치한 경우에는 O(n)
• 평균 경우(Average Case) : O(n)

 

코드 구현 예제(Java 구현)

class SequenceSearch {
    public int sequenceSearch(int[] S, int F) {
        int location = -1;  // 인덱스 기본값은 -1로 설정 (찾지 못했을 때의 값)

        for (int i = 0; i < S.length; i++) {    // 배열의 길이만큼 순차적으로 검사
            if (S[i] == F) {
                location = i;  // 값을 찾으면 그 인덱스를 location에 저장
                break;  // 찾았으면 더 이상 탐색할 필요 없음
            }
        }

        // 찾지 못한 경우 location은 -1로 유지됨 (기본값)
        return location;
    }
}

public class Main {
    public static void main(String[] args) {
        SequenceSearch sequenceSearch = new SequenceSearch();
        int[] S = new int[] {10, 7, 11, 5, 13, 8};  // 배열 S
        int F = 8;  // 찾을 원소

        int location = sequenceSearch.sequenceSearch(S, F);  // 배열 S에서 원소 8을 찾아라

        System.out.println("result : " + location);     // 원소 8의 인덱스를 출력
    }
}

 

순차 검색 알고리즘의 장점과 단점

순차 검색 알고리즘은 데이터가 작을 때는 간단하게 구현할 수 있어 편리하지만 데이터의 양이 많아지면 비효율적이기 때문에 다른 알고리즘을 사용해야 합니다.

 

순차 검색 알고리즘의 장점

알고리즘이 간단하게 처음부터 끝까지 전부 비교해서 검사하는 작업이기 때문에 이에 맞게 코드도 매우 간단하고 정렬되지 않은 상태에서도 사용이 가능하다는 장점이 있습니다.

 

순차 검색 알고리즘의 단점

간단하게 전부 비교하기 때문에 배열의 요소가 많아질수록 비교하는 배열의 요소가 늘어나므로 검색 시간이 매우 오래걸리기 때문에 비효율적입니다.