12장 검색<비교 검색 방식>

비교 검색 방식 - 검색 대상의 키를 비교하여 검색하는 방법 (순차 검색, 이진 검색, 이진 트리 검색)

계산 검색 방식 - 키를 비교하지 않고 계수적인 성질을 이용한 계산으로 검색 하는 방법 (해싱)

 

순차 검색(순차 검색, 색인 순차 검색)

순차검색은 일렬로 되어있는 자료를 처음부터 마지막까지 순서대로 비교하여 검색하는 방법으로, 가장 간단하고 직접적인 방법으로서 배열이나 연결 리스트로 구현된 순차 자료구조에서 원하는 항목을 찾는 방법이다.

 

색인 순차 검색은 인덱스 테이블을 추가로 사용하여 탐색의 효율을 높이는 검색 방법이다. 찾고자 하는 키값을 인덱스 테이블에서 검색하여 indexTable[i].key <= key < indexTable[i+1].key를 만족하는 i를 찾아서 알아낸 범위에 대해서만 순차 검색을 수행한다.

 

이진 검색 

이진 검색은 가운데에 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법을 반복 수행하는 분할 정복 기법을 이용한 검색 방법이다. 이진 검색은 반드시 정렬되어있는 자료에서의 검색에서만 사용할 수 있다.

이진 트리 검색

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