검색 알고리즘, 보초법

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용

 

보초법으로 선형 검색 구현하기

 선형 검색은 반복할 때마다 종료 조건 1, 2를 모두 판단함.
처리할 데이터의 양이 많을수록 종료 조건을 검사하는 비용은 커짐. 보초법은 이 비용을 50%로 낮춤.

 

When found the number 2

 

When not found number 5

 

 

배열 요소 a[0] ~ a[6]은 원래의 데이터이다. 맨 끝 요소 a[7]은 검색하기 전에 값을 추가하여 저장한 보초(sentinel)이다.

보초법을 사용시 아래의 코드와 같이 조건문 수정 가능함.

int i = 0;
a[n] = key;

while (true) {
	if (a[i] == key) break;
	i++;
}

return i == n ? -1 : i;