[자료구조] 검색 (Search)

 검색 / 탐색 (Search) 

 - 컴퓨터에 저장한 자료 중 원하는 항목을 찾는 작업

    ㄴ 검색 성공 - 원하는 항목을 찾은 경우

    ㄴ 검색 실패 - 원하는 항목을 찾지 못한 경우

 - 탐색 키를 가진 항목을 찾는 것

    ㄴ 탐색 키(search key) = 자료를 구별하여 인식할 수 있는 키

 - 삽입 / 삭제 작업에서의 검색

    ㄴ 원소를 삽입하거나 삭제할 위치를 찾기 위해 검색 연산 수행

---

방법

 - 수행 위치에 따른 분류

    ㄴ 내부 검색 : 메모리 내의 자료에 대해 검색 수행

    ㄴ 외부 검색 : 보조 기억 장치에 있는 자료에 대해 검색 수행

 - 검색 방식에 따른 분류

    ㄴ 비교 검색 방식(Comparison Search method) : 검색 대상의 키를 비교하여 검색

        (Ex, 순차 검색, 이진 검색, 트리 검색)

    ㄴ 계산 검색 방식(Non- Comparison method) : 계수적인 성질을 이용한 계산으로 검색

        (Ex, 해싱)

 - 검색 방법의 선택 : 자료구조의 형태와 자료의 배열 상태에 따라 최적의 검색 방법 선택

    ① 정렬되지 않은 순차 자료구조

        => 순차 검색(Sequential Search, 선형 탐색(Linear Search))

    ② 정렬되어 있는 순차 자료구조

        => 이진 검색(Binary Search, 이분 검색, 보간 검색(Interpolation Search))

        => 색인 순차 검색(Index Sequential Search)

    ③ 이진트리

        => 해싱(Hashing)