Sequential Search Algorithm

* 배열의 인덱스가 1부터 시작한다고 가정합니다.

([1] = 1번째 와 같이 이해하기 쉽도록)

 

- 알고리즘 정의

찾고자 하는 원소가 나올 때 까지 인덱스의 처음부터 순차로 탐색하는 알고리즘.

 

- Pseudocode

public static index SeqSearch(int n, keyType[] S, keyType x) {
    index location = 1;
    while (location <= n && S[location] != x)
        location++;
    
    if (location > n)
        location = 0;
    
    return location;
}

크기가 n인 배열 S에서 x를 찾는 알고리즘.

location이 n보다 작거나 x를 발견하지 못할 경우 location을 1씩 증가하며 탐색

찾은 경우, 또는 배열의 끝까지 탐색한 경우 while문을 빠져나온다.

끝까지 탐색한 경우에는 location을 0으로 설정해 탐색하지 못함을 알림.

 

- Time complexity

Basic Operation: S[location] != x 

Input Size: n

 

* Bast case: B(n) = 1 [Θ(1)]

* Worst case: W(n) = n [Θ(n)]

* Average case:

[Θ(n)]