[자료구조] 1201 (2) 13. 탐색

13. 탐색 (searching)

1. 탐색이란?
2. 정렬되지 않은 배열에서의 탐색
3. 정렬된 배열에서의 탐색
4. 이진 탐색 트리 
5. AVL 트리
6. 2-3 트리

---

13.1 탐색이란?

: 여러 개의 자료 중에서 원하는 자료를 찾아내는 작업

• 탐색키(search key): 항목과 항목을 구별해주는 키

 

---

13.2 정렬되지 않은 배열에서의 탐색

• 순차 탐색(sequential search)

순차 탐색(sequential search)

: 정렬되지 않은 sequence, si를 처음부터 마지막까지 순차적으로 하나씩 검사하는 방법

순차 탐색(sequential search)

순차 탐색 - example

 

개선된 순차 탐색

: 리스트 끝에 탐색키를 저장한다. 

--> 탐색에 실패하면, 키 값의 인덱스를 반환한다. (개선된 거 아님...)

개선된 순차 탐색 - example

순차탐색 vs. 개선된 순차탐색

 

---

13.3 정렬된 배열에서의 탐색

• 이진 탐색(binary search)
• 색인 순차탐색(indexed sequential search)
• 보간탐색(interpolation search)

이진 탐색(binary search)

: 정렬된 배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 그 값보다 작은지 큰지 판단하여, 탐색의 범위를 반으로 줄여가며 탐색을 진행한다. --> log(n)

• But, "정렬된 배열"이기 때문에, 레코드의 삽입/삭제가 빈번한 응용에서는 부적절하다.

이진 탐색(binary search)

• 탐색키 값 < middle 값 --> high 포인터를 (middle - 1)로 이동한다.
• 탐색키 값 > middle 값 --> low 포인터를 (middle + 1)로 이동한다.
• 탐색키 == middle 값이면, 탐색 성공이다!

 

이진탐색 프로그램: 순환 vs. 반복

 

 

색인 순차 탐색(indexed sequential search)

: 인덱스 테이블을 먼저 검색하여, 탐색키가 속한 범위를 알아낸 후(이미 정렬된 배열이기 때문에 가능함), 순차탐색한다.

색인 순차 탐색(indexed sequential search)

 

 

보간 탐색(interpolation search)

: 배열[0]과 배열[n-1] 값을 통해 탐색키가 존재할 위치를 예측하여 탐색한다.

보간 탐색(interpolation search)

보간탐색 - example

보간탐색 - 코드

 

---

 

 

 

 

 

출처: 이화여자대학교 이숙영교수님 자료구조