Sequential Search

1. Problem

- n개의 요소가 담긴 배열 S에서 x를 찾아보자

 

2. Input

1) 양수 n

2) 배열 S indexed from 1 to n

3) key x

 

3. Output

1) x의 위치

2) S에 x가 없다면 0을 반환

 

4. PseudoCode

index seqsearch(int n, const keytype[] S, keytype x, index location){
    location = 1;
    while(location<=n && S[location]!=x)
        location++;
    if(location>n)
        location = 0;
    return location;
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int[] arr = {5, 9, 3, 10, 6, 2, 1};
    	int a = 6;
    	int index_a = seqsearch(arr.length, arr, a);
    	System.out.println(a +"의 위치: " + index_a); // 6의 위치: 5
    	int b = 7;
    	int index_b = seqsearch(arr.length, arr, b);
    	System.out.println(b +"의 위치: " + index_b); // 7의 위치: 0
    }
    
    static int seqsearch(int n, int[] S, int x){
    	int location = 0; 
    	while(location<n && S[location]!=x) // 실제 인덱스는 0부터
    		location++;
    	return location<n ? location+1 : 0;
    }
}

- worst T(n) = n (찾는 요소가 가장 마지막에 있을 경우)

- average T(n) = (n+1)/2

- best T(n) = 1 (찾는 요소가 맨 앞에 있을 경우)