검색 알고리즘
검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다.
- 원하는 값을 찾기 위해서는 키(key) 값이 필요하다. 서울에 사는 사람을 찾기 위해서는 키값을 '서울' 로 지정해야 한다. 20세 이상 30세 미만인 사람을 찾기 위해서는 키 값을 20세 이상 30세 미만 으로 설정해야 한다. 대부분의 경우에서 키는 데이터의 일부이다.
선형 검색
무작위로 늘어놓은 데이터 모임에서 검색을 수행하는 방법이다.
요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.
키 값이 '1' 이라면 세번째 시도에서 성공하고, 키 값이 '4' 라면 검색에 실패한다.
선형 검색 종료 조건
다음 조건 중 하나라도 성립하면 검색을 종료한다.
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
- 검색할 값과 같은 요소를 발견한 경우
선형검색 구현
//배열 a의 앞쪽 n개의 요소에서 key 와 같은 요소를 선형 검색한다.
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번 조건만 맞는지 판단을 한다.
a[0]~a[3] 에서 값을 찾지 못하면 a[4] 에 도달하게 되고 2번 조건이 성립해 검색을 종료한다.
보초법 구현
//요솟수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색한다.
int seqSearchSen(int[] a, int n, int key){
a[n] = key; //보초를 추가
for(int i=0; i<n+1; i++){
if(a[i] == key){
return i; //검색 성공시 인덱스 반환
}
}
return -1; //검색 실패시 -1을 반환
}
참고
자료구조와 함께배우는 자바 알고리즘 입문