C언어 기초/자료구조/C로 배우는 쉬운 자료구조/Chapter10 검색_1

반응형

검색

 검색 search란 말 그대로 무언가를 찾는 것입니다!

 저장한 자료 중 원하는 자료를 찾았다면 검색 성공 Hit!

 찾지 못했다면 검색 실패 Miss!

---

검색은 위치에 따라

• 내부 검색 Internal Search: 메모리 내에서 수행
• 외부 검색 External Search: 메모리 외부 보조 기억 장치에서 수행

으로 나눌 수 있습니다.

 

또한 검색 방법에 따라

• 비교 검색 Comparison Search: 검색 대상의 키를 비교하여 검색한다(순차 검색, 이진 검색, 트리 검색)
• 계산 검색 Non-Comparison Search: 계수적인 성질을 이용한 계산으로 검색한다(해싱)

으로 나눌 수 있습니다.

---

비교 검색

---

1. 순차 검색

 가장 쉽고 단순한 방법으로 

• 기본 순차 검색: 항목을 순서대로 비교하면서 검색
• 색인 순차 검색: 검색의 효율을 높이기 위해 인덱스 테이블 사용

이 있습니다.

---

1) 순차 검색(기본 순차 검색)

•     기본 순차 검색 Basic Sequential Search == 선형 검색 Linear Search

 순차 검색 Sequential Search은 일렬로 나열된 자료를 처음부터 마지막까지 순서대로 검색하는 방법입니다.

---

 

    1. 정렬되어 있지 않은 자료를 순차 검색

 

• 첫째 원소부터 마지막 원소까지 순서대로 키값이 일치하는 원소가 있는지 비교하여 찾습니다.
• 평균 시간 복잡도: O(n)

평균 비교 횟수는 1/n *(n*(n+1)/2) = (n+1)/2 : 평균 시간 복잡도 O(n)

 

정렬되지 않은 자료를 순차 검색

#include <stdio.h>    typedef int element;    void sequentialSearch(element a[ ], int n, element key){          int  i = 0;          while( i < n && a[ i ]  !=  key)   i++;          if( i < n)    printf("검색 성공!");          else    printf("검색 실패!);    }

element a[ ] : 검색할 배열 int n :  배열의 크기 element key : 찾고자하는 자료의 데이터 data

 

 

     2. 정렬된 자료를 순차 검색

   

• 검색이 끝나는 시점이 달라집니다!
• 비교하는 원소의 키값이 찾는 키값보다 크면 찾는 원소가 없는 것! 검색 끝!
• 평균 시간 복잡도: O(n)

평균 비교 횟수가 반으로 줄어들었지만 평균 시간 복잡도에는 영향을 미치지 않는다!!

 

정렬된 자료를 순차 검색

#include <stdio.h>    typedef int element;    void sequentialSearch(element a[ ], int n, element key){          int  i = 0;          while( i < n && a[ i ]  <  key)   i++;          if(a[ i ] == key)    printf("검색 성공!");          else    printf("검색 실패!);    }

element a[ ] : 검색할 배열 int n :  배열의 크기 element key : 찾고자하는 자료의 데이터 data

---

2) 색인 순차 검색

 

 색인 순차 검색 Index Sequential Search 또는 인덱스 순차 검색

• 정렬된 자료를 검색
• 인덱스 테이블 Index Table 사용
• 탐색의 범위를 줄여줌 => 검색 효율 UP!
• 평균 시간 복잡도: O(m + n/m) - n: 검색 배열 크기, m: 인덱스 테이블의 크기

---

인덱스 테이블 Index Table

 

배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때

n/m 간격으로 떨어져 있는 원소와 인덱스를 인덱스 테이블에 저장!

 

index	key
0	1
3	9
6	29

 

평균 시간 복잡도에 인덱스 테이블의 크기도 들어가기 때문에

인덱스 테이블의 크기와 검색 시간과의 관계를 고려하여 인덱스 테이블의 크기를 정해야 합니다!

---

2. 이진 검색

이진 검색 Binary Search(보간 검색 Interpolation Search , 이분 검색)은 자료 가운데 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색하고, 더 작으면 왼쪽 부분을 검색하는 방법입니다.

검색 범위를 반으로 줄여 가면서 빠르게 검색합니다.

이진 검색을 하는 자료는 반드시 정렬되어 있어야 합니다!

 

• 정렬된 자료, 자료 1/2 지점 항목과 키값 비교
• 항목 > key 이면 오른쪽 부분 검색, 항목 < key 이면 왼쪽 부분 검색
• 분할 정복 기법 이용(Divide and Conquer): 검색 범위를 반으로 분할하고 검색하는 작업 반복
• 평균 시간 복잡도: O(log₂ n)

 

정렬된 자료를 이진 검색

binarySearch.c

#include <stdio.h> typedef int element; int cnt = 0; void binarySearch( element a[ ], int begin, int end, element key){       int middle;       cnt++;       if(begin == end){             if(key == a[begin])   printf("%3d번째에 검색 성공!", cnt);             else printf("검색 실패!");             return 0;       }       middle = (begin + end) / 2;       if(key == a[middle])    printf("%3d번째에 검색 성공!", cnt); //키값이 middle과 같을 경우       else if(key<a[middle] &&(middle -1 >= begin)) // 키값이 middle 보다 작은 경우 -> 왼쪽 검색             binarySearch(a, begin, middel -1, key);       else if (key > a[middle] && (middle + 1 <= end)) // 키값이 middle 보다 큰 경우 -> 오른쪽 검색             binarySearch(a, middle+1, end, key);       else   printf("검색 실패!"); }

binarySearch_ex.c

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> typedef int element; int main(void){ element a[ ] = {1, 2, 8, 9, 11, 19, 29}, key; int i, size = sizeof(a) / sizeof(a[0]); char more; extern int cnt; for(i = 0; i<size;i++) printf("%5d", a[i]); puts(""); do{ cnt = 0; printf("검색할 키를 입력하세요 : "); scanf("%d", &key); binarySearch(a, 0, size -1, key); printf("검색을 계속하려면 y를 누르세요>>"); scanf("%c", &more); } while(more == 'y'); getchar(); return 0; }

---

3. 이진 트리 검색

• 이진 트리 검색 Binary Tree Search은 이진 탐색 트리를 사용하여 검색하는 방법! 입니다.

이진 탐색 트리는 루트 노드를 기준으로 왼쪽 서브 트리는 루트 노드보다 키값이 작은 원소로 구성하고 오른쪽 서브 트리는 루트 노드보다 키값이 큰 원소로 구성한 이진 트리 입니다.

 

이진 탐색과 비슷해 보이나 트리를 사용하고 자료가 정렬되어 있지 않습니다!

• 이진 탐색 트리의 특성을 이용하여 쉽게 검색
• 원소 삽입이나 삭제 연산에 대해 항상 이진 탐색 트리를 재구성해 유지해야함
• 전체 출력하면 트리를 중위 순회하며 트리에 모든 단어를 정렬함(p.593)
•  

2023.12.15 - [C언어 기초/자료구조] - C언어 기초/자료구조/C로 배우는 쉬운 자료구조/Chapter10 검색_2

C언어 기초/자료구조/C로 배우는 쉬운 자료구조/Chapter10 검색_2