3-2장 검색 알고리즘 - 선형(순차)검색 | 보초법 검색

 

해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다.

---

3-2장 검색 알고리즘 - 선형(순차)검색 | 보초법 검색

선형 검색 linear search  / 순차 검색 sequence search

- 요소가 직선 모양으로 늘어선 배열

- 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.

 

 

선형 검색에서 배열 검색의 종료조건 2가지

1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
2. 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공

 

 

배열 요수에 따른 검색 수행 횟수

배열의 요소의 개수가 n개일 때 [2️⃣−1️⃣], [2️⃣−2️⃣] 조건을 판단하는 횟수는 평균 n/2회이다.
* [2️⃣−1️⃣]은 n +1회
* [2️⃣−2️⃣]는 n회 수행한다. 

 

 

요소 개수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드

int i = 0;
while(1){
	// 검색 실패
	if(i == n) 
	return -1;

	// 검색 성공
	if (a[i] == key)
	return i;
	i++;
}

 

[ int i = 0 ]  

- 배열의 인덱스를 가르키는 변수

- 0으로 초기화 ( = 0번째 인덱스 부터 검색하겠다.)

 

[ while(1) ]

- 계속 반복하도록 하기위해 의도적으로 넣은 값

- while 문을 반복할 때 계속해서 실행할지에 대한 판단은 '1'로 판단한다. 

 

[ return -1 ]

- 검색 실패 시 반환하는 -1은 배열의 인덱스로는 있을 수 없는 값이다.

- 함수를 호출하는 쪽에서 검색에 성공했는지 쉽게 판정할 수 있다. 

 

[ i++ ]

- 요소를 하나 검색할 때마다 while 문이 제어하는 루프 본문의 끝에서 1씩 증가시킨다. 

 

선형 검색와 보초법 검색의 차이

1. 선형 검색
- 반복할 때마다 종료조건 2가지(검색 실패, 검색 성공)를 모두 체크한다. 

2. 보초법 검색
- 반복할 때마다 종료조건 중 1가지(검색 성공)만 체크한다. 
- 종료 조건이 1가지이기 떄문에 종료 조건을 검사하는 비용이 절반(50%)으로 줄어든다.

 

보초법(sentinel method)으로 검색하기

 

보초법 검색 방법

1. 배열의 끝에 보초자리를 하나 더 생성한다. 
2. 검색 시작할 때 보초자리에 검색하는 값을 임시로 넣어 둔다.
3. 검색하는 값이 배열에서 검색 성공 시 검생 성공이 된다.
4. 만약 검색하는 값이 배열에 없다면 보초자리에 있는 임시 값으로 검색 성공이 된다. 
5. 이렇게 "검색 성공" 종료조건만 가지고 선형 검색을 진행한다.  

 

 

일반 선형 검색 코드와 보초법 선형 검색 코드

왼(일반 선형 검색)   오(보초법 선형 검색)