[알고리즘] 탐색 알고리즘 - 선형 탐색 Linear Search

 

선형 탐색(Linear Search) 알고리즘 or 순차 탐색(Sequential Search) 알고리즘 :

요소가 직선 모양으로 늘어진 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 탐색

 

배열 Linear

위 배열에서 요소를 탐색하면

탐색 성공                                                                               탐색 실패

값 5를 탐색하면 Linear[2] 에서 탐색에 성공하지만

값 3을 탐색하면 Linear에 값 3이 존재하지 않기 때문에 탐색에 실패한다. 

 

위 예시를 보면 배열 탐색의 종료 조건이 다음 2개임을 알 수 있다.

   조건 1 : 탐색할 값과 같은 요소를 발견한 경우 (탐색 성공)

   조건 2 : 탐색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (탐색 실패)

배열의 요소 수가 n개 일 때 조건 1,2를 판단하는 횟수는 평균 n/2회 이다. => O(n)

 

 

메서드 seqSearch() : 배열 a 의 처음부터 끝까지 총 n개의 요소 중에서 값이 key인 요소를 선형 탐색

매개변수 : int[] a, int n, int key

반환값 : 키 값이 여러개 존재할 경우, 처음 발견한 요소의 인덱스를, 키 값이 존재하지 않으면 -1을 반환

 

- while문으로 구현한 경우

     조건 1 : a[i] == key (탐색 성공)

     조건 2 : i == n (탐색 실패)

int seqSearch(int[] a, int n, int key) {
	int i = 0;
	
	while(true) {
		if(i == n) {
			return -1;
		}
		if(a[i] == key) {
			return i;
		}
		i++;
	}
}

 

- for문으로 구현한 경우

     조건 1 : a[i] == key (탐색 성공)

     조건 2 : for문 종료 (탐색 실패)

int seqSearch(int[] a, int n, int key) {
	for(int i = 0; i < n; i++) {
		if(a[i] == key) {
			return i;
		}
	}
	return -1;
}

 

보초법 : 

선형 탐색은 반복할 때 마다 조건 1과 2를 모두 판단. 탐색하기 전 탐색하고자 하는 키 값을 배열의 요소 맨 끝에 추가. 키 값을 찾지 못했을 때를 판단하는 종료 조건 2가 필요하지 않게 만들어 판단 횟수를 반으로 줄인다.

보초법

값 5를 탐색하면 탐색에 성공하지만

값 3을 탐색하면 배열의 맨 마지막에서 키 값을 발견, 탐색에 성공하지만 배열의 기존 값이 아닌 직접 추가한 보초(Sentinel)이다.

 

조건 1 : a[i] == key (탐색 성공)

+ return i == n ? -1 : i (찾은 값이 원래 배열의 데이터인지 추가한 보초인지 판단)

static int seqSearchSen(int[] a, int n, int key) {
	int i = 0;
	
	a[n] = key;
	
	while(true) {
		if(a[i] == key) {
			break;
		}
		i++;
	}
	return i == n ? -1 : i ;
}

 

 

 

 

 

선형 탐색 Linear Search : O(N)