[Do it 알고리즘] 03. 검색
03. 검색
03-1. 검색 알고리즘
검색과 키
검색
- 배열 검색
- 선형 검색 : 무작위로 늘어 놓은 데이터 모임에서의 검색
- 이진 검색 : 일정한 규칙으로 늘어 놓은 데이터 모임에서의 아주 빠른 검색
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서의 아주 빠른 검색
- 선형 리스트 검색
- 이진검색트리 검색
03-2. 선형 검색
선형 검색
요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 방식
배열 검색의 종료 조건(판단 횟수 : 평균 n/2 회)
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(판단 횟수 : n+1 회)
- 검색할 값과 같은 요소를 발견한 경우(판단 횟수 : n회)
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(버전 1 : for문) ---*/
int search(const int a[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == key)
return i; /* 검색 성공 */
return -1; /* 검색 실패 */
}
보초법
종료 조건을 검사하는 비용을 반(50%)으로 줄이는 방법
int search(int a[], int n, int key)
{
int i = 0;
a[n] = key; /* 보초를 추가 */
while (1) {
if (a[i] == key)
break; /* 원하는 키 값을 찾은 경우 */
i++;
}
return i == n ? -1 : i;
}
03-3. 이진 검색
이진 검색
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
1. a[pc] < key 일 때
- 선형 검색 : 무작위로 늘어 놓은 데이터 모임에서의 검색
- 이진 검색 : 일정한 규칙으로 늘어 놓은 데이터 모임에서의 아주 빠른 검색
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서의 아주 빠른 검색
요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 방식
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(버전 1 : for문) ---*/
int search(const int a[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == key)
return i; /* 검색 성공 */
return -1; /* 검색 실패 */
}
종료 조건을 검사하는 비용을 반(50%)으로 줄이는 방법
int search(int a[], int n, int key)
{
int i = 0;
a[n] = key; /* 보초를 추가 */
while (1) {
if (a[i] == key)
break; /* 원하는 키 값을 찾은 경우 */
i++;
}
return i == n ? -1 : i;
}
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외
검색 범위는 a[pc+1] ~ a[pr]로 좁혀짐
pl의 값을 pc+1로 업데이트
2. a[pc] > key 일 때
a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외
검색 범위는 a[pl] ~ a[pc-1]로 좁혀짐
pr의 값을 pc-1로 업데이트
이진 검색 알고리즘의 종료 조건
- a[pc]와 key가 일치하는 경우
- 검색 범위가 더 이상 없는 경우
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 이진 검색 ---*/
int bin_search(const 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;
else
pr = pc - 1;
} while (pl <= pr);
return -1; /* 검색 실패 */
}
복잡도(complexity)
알고리즘의 성능을 객관적으로 평가하는 기준
- 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
- 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
선형 검색의 시간 복잡도
int search(const int a[], int n, int key)
{
/*l1*/ int i = 0;
/*l2*/ while (i < n) {
/*l3*/ if (a[i] == key)
/*l4*/ return i; /* 검색 성공 */
/*l5*/ i++;
}
/*l6*/ return -1; /* 검색 실패 */
}
l1 : 변수 i에 0을 대입하는 횟수가 1회이므로 O(1)
l4, l6 : 함수에서 값을 반환하는 시행이 한 번이므로 O(1)
l2 : 배열의 맨 끝에 도달했는지 판단 - 처음부터 도달하면 1, 마지막에 도달하면 n이므로 평균 실행 횟수는 n/2
l3 : 현재 검사하고 있는 요소와 찾고자 하는 값이 같은지 판단 - l2와 같은 이유로 평균 실행 횟수는 n/2
따라서 시간 복잡도는 O(n)
🔴 이진 검색의 시간 복잡도
int bin_search(const int a[], int n, int key)
{
/*l1*/ int pl = 0; /* 검색 범위 맨 앞의 인덱스 */
/*l2*/ int pr = n - 1; /* 검색 범위 맨 끝의 인덱스 */
do {
/*l3*/ int pc = (pl + pr) / 2; /* 중앙 요소의 인덱스 */
/*l4*/ if (a[pc] == key)
/*l5*/ return pc; /* 검색 성공 */
/*l6*/ else if (a[pc] < key)
/*l7*/ pl = pc + 1; /* 검색 범위를 뒤쪽 반으로 줄임 */
/*l8*/ else
/*l9*/ pr = pc - 1; /* 검색 범위를 앞쪽 반으로 줄임 */
/*l10*/ } while (pl <= pr);
/*l11*/ return -1; /* 검색 실패 */
}
단계 | 실행 횟수 | 복잡도 | 비고 |
---|---|---|---|
l1 | 1 | O(1) | 대입 |
l2 | 1 | O(1) | 대입 |
l3 | log n | O(log n) | 급격->완만 감소 |
l4 | log n | O(log n) | |
l5 | 1 | O(1) | 반환 |
l6 | log n | O(log n) | |
l7 | log n | O(log n) | |
l8 | log n | O(log n) | |
l9 | log n | O(log n) | |
l10 | log n | O(log n) | |
l12 | 1 | O(1) | 반환 |
따라서 시간 복잡도는 O(log n)
* 참고 : [알고리즘] 3. 시간복잡도(BigO) 기초 - 센치한개발자
Author And Source
이 문제에 관하여([Do it 알고리즘] 03. 검색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dkswlgus00/Do-it-알고리즘-03.-검색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)