13. 탐색 (searching)
- 탐색이란?
- 정렬되지 않은 배열에서의 탐색
- 정렬된 배열에서의 탐색
- 이진 탐색 트리
- AVL 트리
- 2-3 트리
13.1 탐색이란?
: 여러 개의 자료 중에서 원하는 자료를 찾아내는 작업
- 탐색키(search key): 항목과 항목을 구별해주는 키
13.2 정렬되지 않은 배열에서의 탐색
- 순차 탐색(sequential search)
순차 탐색(sequential search)
: 정렬되지 않은 sequence, si를 처음부터 마지막까지 순차적으로 하나씩 검사하는 방법
개선된 순차 탐색
: 리스트 끝에 탐색키를 저장한다.
--> 탐색에 실패하면, 키 값의 인덱스를 반환한다. (개선된 거 아님...)
13.3 정렬된 배열에서의 탐색
- 이진 탐색(binary search)
- 색인 순차탐색(indexed sequential search)
- 보간탐색(interpolation search)
이진 탐색(binary search)
: 정렬된 배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 그 값보다 작은지 큰지 판단하여, 탐색의 범위를 반으로 줄여가며 탐색을 진행한다. --> log(n)
- But, "정렬된 배열"이기 때문에, 레코드의 삽입/삭제가 빈번한 응용에서는 부적절하다.
- 탐색키 값 < middle 값 --> high 포인터를 (middle - 1)로 이동한다.
- 탐색키 값 > middle 값 --> low 포인터를 (middle + 1)로 이동한다.
- 탐색키 == middle 값이면, 탐색 성공이다!
색인 순차 탐색(indexed sequential search)
: 인덱스 테이블을 먼저 검색하여, 탐색키가 속한 범위를 알아낸 후(이미 정렬된 배열이기 때문에 가능함), 순차탐색한다.
보간 탐색(interpolation search)
: 배열[0]과 배열[n-1] 값을 통해 탐색키가 존재할 위치를 예측하여 탐색한다.
출처: 이화여자대학교 이숙영교수님 자료구조
'자료구조' 카테고리의 다른 글
[자료구조] 1205 (2) 14. 해싱 (1) | 2023.12.07 |
---|---|
[자료구조] 1205 (1) (1) | 2023.12.07 |
[자료구조] 1201 (1) (0) | 2023.12.05 |
[자료구조] 1128 (0) | 2023.12.05 |
[자료구조] 1124 (1) | 2023.12.02 |