SW Expert Academy 의 SW문제해결 기본 Array 2 강좌 - 3차시 주제입니다.
검색은 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업, 즉 목적하는 탐색키를 가진 항목을 찾는 것이라 할 수 있습니다.
검색의 종류에는
- 순차 검색, 이진 검색, 인덱싱
등이 있습니다.
순차 검색
순차 검색은 말 그대로 일렬로 되어 있는 자료를 순서대로 검색하는 방법입니다.
배열이나 연결 리스트 등 순차 구조로 구현된 자료구조에서 유용하며 구현이 쉽습니다.
하지만 검색 대상이 많은 경우 수행시간이 매우 증가할 수 있어 비효율적입니다.
순차 검색 - 정렬되지 않은 자료의 검색 과정 (O(n))
- 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하여 찾음
- 키 값이 동일한 원소를 찾으면 그 원소의 인덱스 반환
- 마지막까지 찾지 못하면 실패
그러므로 n개의 자료가 있을 때 특정한 원소를 찾는 순차 검색 알고리즘의 시간 복잡도는 O(n)이 됩니다.
순차 검색 - 정렬된 자료의 검색 과정 (O(n))
- 자료가 오름차순으로 정렬된 상태라 가정하고 검색 실시
- 자료를 순차적으로 처음부터 검색하면서 키 값 비교
- 원소 키 값이 검색 대상의 키 값보다 크다면, 검색 대상인 키가 없다는 의미이므로 검색을 종료함
자료가 이렇게 정렬되어 있을 경우, 정렬되지 않은 자료와 다르게 검색 실패를 반환하는 경우일 때 평균 비교 횟수가 반으로 줄어듭니다.
정렬되지 않은 자료는 검색하고자 하는 키 값을 찾기 위해 처음부터 끝까지 탐색하지만,
정렬된 자료는 어느 시점에 원소가 찾고자 하는 키값보다 커진다면 검색을 종료하므로 굳이 끝까지 탐색을 시도하지 않을 수 있기 때문입니다.
이진 검색
이진 검색은 검색을 진행할 때마다 검색 범위를 반씩 줄여나가면서 빠르게 검색을 수행할 수 있습니다. 그래서 순차 검색보다 효율적이라고 할 수 있습니다.
단, 이진 검색을 수행하려면 자료가 정렬되어 있다고 가정해야 합니다.
자료의 중앙에 있는 항목의 키 값과, 찾고자 하는 대상의 값을 비교한 후 다음 검색 위치(가운데의 왼쪽 구역 혹은 오른쪽 구역)를 결정한다.
- 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다.
- 이진검색은, 자료에 삽입이나 삭제가 발생한다면 자료의 상태를 항상 정렬 상태로 유지해야 하는 추가적인 작업이 필요하다.
이진 검색 - Pseudo code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
binarySearch(int *arr, key){
int start = 0;
int end = arrlen - 1;
while(start <= end){ // start가 end보다 작거나 같을 때까지 진행.
// 만일 start가 end보다 커지면 검색을 더 이상 진행할 수 없으므로 종료
if(arr[middle] == key){
return true; // 검색 성공
}
else if (arr[middle] > key){
end = middle - 1;
}
else
start = middle + 1;
}
return false;
}