- 용도나 목적, 실행 속도, 자료구조 등을 고려하여 검색 알고리즘을 선택해야 함
- 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색 수행
- 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색 수행
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색 수행
- 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
선형 검색 (순차 검색)
- 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색
//요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색
int search(int a[], int n, int key) {
for (int i = 0; i < n; i++)
if (a[i] == key) return i; //검색 성공
return -1; //검색 실패
}
- 보초법 : 종료 조건을 검사하는 비용을 줄이는 방법
int search(int a[], int n, int key) {
a[n] = key; //보초 추가 (키 값을 맨 끝 요소에 저장)
while(1) {
if (a[i] == key) break;
i++;
}
return i == n ? -1 : i;
}
이진 검색
- 전제 조건 : 데이터가 키 값으로 이미 정렬되어 있음
- 선형 검색보다 좀 더 빠름
int bin_search(int a[], int n, int key) {
int pl = 0; //검색 범위 맨 앞 인덱스
int pr = n - 1; //검색 범위 맨 끝 인덱스
int pc; //검색 범위 한가운데 인덱스
do {
pc = (pl + pr) / 2;
if (a[pc] == key) return pc; //검색 성공
else if (a[pc] < key) pl = pc + 1; //검색 범위는 a[pc + 1] ~ a[pr]로 변경
else pr = pc - 1; //a[pc] > key일 때 검색 범위는 a[pl] ~ a[pc - 1]로 변경
} while (pl <= pr);
return -1; //검색 실패
}