순차 검색(Sequential Search)

순차 검색(Sequential Search) = 선형 검색(Linear Search)

일렬로 되어 있는 자료를 처음부터 끝까지 순서대로 검색.

자료의 양에 따라 효율이 달라지기 때문에 많은 양의 자료를 대상으로는 비효율적.

알고리즘이 단순하여 구현이 쉽고 가장 간단한 방법이다.

​

정렬이 되어 있지 않은 순차 자료구조에서의 순차 검색

자료구조의 처음 원소부터 마지막 원소까지 키 값이 일치하는지 비교한다.

일치하는 원소를 찾으면 몇 번째 원소인지 반환하고 찾지 못하면 검색 실패가 된다.

찾고자 하는 원소의 위치에 따라 비교 횟수가 달라지므로 평균 비교 횟수는 (n+1)/2 이고 시간 복잡도는 O(n)이다.

​

예시 1) 50을 찾는 경우

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

​

예시 2) 검색 실패인 경우

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===>

{57, 16, 41, 2, 50, 6, 32, 27}

===> 종료. 검색 실패.

​

정렬이 되어 있는 순차 자료구조에서의 순차 검색

위와 마찬가지로 자료구조의 처음 원소부터 마지막 원소까지 키 값이 일치하는지 비교한다. 하지만 원소의 키 값이 찾는 키 값보다 크면 찾는 원소가 없다 판단하고 검색 실패로 처리한다.

검색 실패하는 경우는 평균 비교 횟수가 반으로 줄어들지만 시간 복잡도는 똑같이 O(n)이다.

​

예시 1) 27을 찾는 경우

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

​

예시 2) 30을 찾는 경우

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

===> 32가 30보다 크므로 종료. 검색 실패.

​

프로그램 작성)

package test;

class Search {
	public void unsortedSequentialSearch(int[] a, int size, int key) {
		int i = 0;
		
		while(i < size && a[i] != key) {
			i++;
		}
		
		if(i < size) {
			System.out.printf("%d 번째 성공! ", i + 1);
		} else {
			System.out.printf("%d 번째 실패! ", i + 1);
		}
	}
	
	public void sortedSequentialSearch(int[] a, int key) {
		int i = 0;
		
		while(a[i] < key) {
			i++;
		}
		
		if(a[i] == key) {
			System.out.printf("%d 번째 성공! ", i + 1);
		} else {
			System.out.printf("%d 번째 실패! ", i + 1);
		}
	}
}

public class Test {
	public static void main(String[] args) {
		int[] a = {57, 16, 41, 2, 50, 6, 32, 27};

		System.out.println("정렬되지 않은 배열 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Search s = new Search();
		s.unsortedSequentialSearch(a, a.length, 32);
		System.out.println();

		int[] b = {2, 6, 16, 27, 32, 41, 50, 57};

		System.out.println("정렬된 배열 : ");
		for(int i=0; i<b.length; i++) {
			System.out.printf(" %d", b[i]);
		}
		System.out.println();

		s.sortedSequentialSearch(b, 33);
		System.out.println();
		
	}
}

실행 결과)