선형 검색 알아보기
요소가 직선 모양으로 늘어선 배열에서 원하는 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로요소를 검색하는 알고리즘입니다. 선형검색 또는 순차검색이라 합니다.
다음은 [6,4,3,2,1]의 값을 가진 5개의 요소로 구성된 배열에서 2 를 찾는 순서입니다:
- 인덱스가 0인 요소 6을 선택 합니다.
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| value | 6 | 4 | 3 | 2 | 1 |
- 인덱스가 1인 요소 4을 선택 합니다.
| index | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| value | 4 | 3 | 2 | 1 |
- 인덱스가 2인 요소 3을 선택 합니다.
| index | 2 | 3 | 4 | ||
|---|---|---|---|---|---|
| value | 3 | 2 | 1 |
- 인덱스가 3인 요소 2을 선택 합니다. 검색 완료!
| index | 3 | 4 | |||
|---|---|---|---|---|---|
| value | 2 | 1 |
다음 조건중 하나라도 성립하면 검색을 종료합니다.
- 종료조건 1 : 검색할 값을 발견하지 못하고 배열의 끝은 지나간 경우(검색 실패)
- 종료조건 2 : 검색할 값과 같은 요소를 발견한 경우(검색 성공)
다음은 위에 나열된 설명을 토대로 요솟수가 n개인 배열 a에서 값이 key인 요소를 검색하는 코드입니다:
int i = 0
while (true){
if(i == n)
return -1; //종료조건 1 성립
if(a[i] == key)
return i; //종료조건 2 성립
i++;
}보초법으로 선형 검색 구현하기
선형 검색은 반복시마다 종료조건 1과 2를 모두 판단합니다. 이 종료조건을 검사하는 판단비용을 반(50%)으로 줄이는 방법이 보초법입니다.
int i = 0
a[n] = key; //마지막요소에 보초값 추가
while (true){
if(a[i] == key)
break; //검색 성공, 검색하는 값이 없다면 마지막 보초값에 의해 break 수행
i++;
}
return i == n ? -1 : i; //검색 결과에 따라 결과 반환결과적으로 if 연산은 1회 더 수행하지만 종료에 대한 판단 횟수는 절반가량 줄어듭니다.
실무에서의 사용
for(i = 0 ; i < a.length ; i++){
if(a[i] == key) return i; //검색 성공
}
return -1; //검색 실패값을 찾는 즉시 종료하거나 반복문이 종료 될 때 까지 값을 찾지 못한다면 종료합니다. 위의 보초법 사용보다 비용을 무조건 줄일 수 있는 방식입니다.
언뜻보면 보초법을 사용한 경우가 비효율적일 수 있겠으나 책에서는 보초법에 대한 설명을 위해 넣은 것이라 추측됩니다.
이진 검색 알아보기
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다.
다음은 [5,7,15,28,29,31,39,58,68,70,95]의 값으로 구성된 A배열에서 39 를 찾는 순서입니다:
- 요소 A[5](31)을 선택 합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 5 | 7 | 15 | 28 | 29 | 31 | 39 | 58 | 68 | 70 | 95 |
- 검색할 값인 39는 A[5]보다 큽니다. 그러므로 검색 범위를 A[6]~A[10]으로 좁힌 뒤 중앙에 위치한 요소 A[8](68)을 선택합니다.
| index | 6 | 7 | 8 | 9 | 10 | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 39 | 58 | 68 | 70 | 95 |
- 검색할 값인 39는 A[8]보다 작습니다. 그러므로 검색 범위를 A[6]~A[7]으로 좁힌 뒤 중앙의 앞쪽 요소 A[6](39)을 선택합니다.
| index | 6 | 7 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| value | 39 | 58 |
- A[6](39)은 검색한 값과 일치합니다.
검색범위를 좁혀가는 방법은 다음과 같습니다.
- 중앙값 a[pc]가 key보다 작을 때 : 중앙 바로 오른쪽 인덱스를 새로운 검색범위의 pl로 하여 뒤쪽으로 좁힙니다.
- 중앙값 a[pc]가 key보다 클 때 : 중앙 바로 왼쪽 인덱스를 새로운 검색범위의 pr로 하여 앞쪽으로 좁힙니다.
pc는 중앙요소, pl은 검색범위의 맨 앞 요소, pr은 검색범위의 맨 뒤 요소를 뜻합니다.
다음 조건중 하나라도 성립하면 검색을 종료합니다.
- 종료조건 1 : a[pc]와 key가 일치하는 경우
- 종료조건 2 : 검색범위가 더 이상 없는 경우
다음은 위에 나열된 설명을 토대로 요솟수가 n개인 배열 a에서 값이 key인 요소를 검색하는 코드입니다:
int pl = 0;
int pr = n - 1;
do {
int pc = (pl + pr)/2 //중앙요소 인덱스
if(a[pc] == key) return pc; //종료조건 1 : 검색 성공
else if (a[pc] < key) pl = pc + 1; //검색범위를 뒤로 좁힘
else (a[pc] > key) pr = pc - 1; //검색범위를 앞으로 좁힘
} while (pc <= pr);
return -1; //종료조건 2 : 검색 실패복잡도 구하기
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 합니다. 복잡도는 다음 두가지 요소를 가집니다.
- 시간 복잡도 : 실행에 필요한 시간을 평가
- 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가
선형 검색의 시간 복잡도
이전에 사용한 선형 검색 함수를 바탕으로 복잡도를 살펴봅니다.
int i = 0 //단계1
while (i < n){ //단계2
if(a[i] == key) //단계3
return i; //단계4
i++; //단계5
}
return -1; //단계6| 단계 | 실행 횟수 | 복잡도 | 설명 |
|---|---|---|---|
| 1 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
| 2 | n/2 | O(n) | 평균 실행횟수는 n/2라고 판단 |
| 3 | n/2 | O(n) | 평균 실행횟수는 n/2라고 판단 |
| 4 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
| 5 | n/2 | O(n) | 평균 실행횟수는 n/2라고 판단 |
| 6 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
일반적으로 O(f(n)) 과 O(g(n))의 시간 복잡도를 계산하는 방법은 다음과 같다.
그러므로 선형 검색의 복잡도는 다음과 같다.
이진 검색의 시간 복잡도
이진 검색의 시간 복잡도를 살펴봅니다.
int pl = 0;
int pr = n - 1;
do {
int pc = (pl + pr)/2 //중앙요소 인덱스
if(a[pc] == key) return pc; //종료조건 1 : 검색 성공
else if (a[pc] < key) pl = pc + 1; //검색범위를 뒤로 좁힘
else (a[pc] > key) pr = pc - 1; //검색범위를 앞으로 좁힘
} while (pc <= pr);
return -1; //종료조건 2 : 검색 실패| 단계 | 실행 횟수 | 복잡도 | 설명 |
|---|---|---|---|
| 1 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
| 2 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
| 3 | log n | O(log n) | 검색할 요소의 범위가 줄어듬 |
| 4 | log n | O(log n) | 검색할 요소의 범위가 줄어듬 |
| 5 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
| 6 | log n | O(log n) | 검색할 요소의 범위가 줄어듬 |
| 7 | log n | O(log n) | 검색할 요소의 범위가 줄어듬 |
| 8 | log n | O(log n) | 검색할 요소의 범위가 줄어듬 |
| 9 | log n | O(log n) | 검색할 요소의 범위가 줄어듬 |
| 10 | 1 | O(1) | 1회 실행 후 이후 실행 안함 |
이진 검색의 복잡도는 다음과 같다.