탐색(Search)

탐색(Search)

테이블(Table)에서 원하는 탐색키(Search Key)를 가진 레코드(Record)를 찾는 작업

 

맵(Map)/사전(Dictionary)

자료를 저장하고 탐색키를 이용해 원하는 자료를 빠르게 찾을 수 있도록하는 탐색을 위한 자료구조

엔트리(Entry)라 칭해지는 키(Key) - 값(Value)쌍의 집합으로 이루어져 있으며 중복을 허용하지 않는다.

 

 

Map의 추상자료형

데이터

엔트리의 집합

 

연산

search(key): key를 가진 엔트리를 찾아 리턴

insert(entry): 엔트리를 맵에 삽입

delete(key): key를 가진 엔트리를 삭제

 

 

순차 탐색(Sequential Search)

데이터 배열의 처음부터 끝까지 하나씩 검사하여 원하는 데이터를 찾는 방법

정렬되지 않은 배열에서도 탐색키를 찾을 수 있으나 비효율적인 방법이다.

 

 

시간 복잡도: O(n)

 

 

이진 탐색(Binary Search)

데이터 배열의 중앙에 있는 값을 조사해서 찾고자 하는 항목이 왼쪽에 있는지 오른쪽에 있는지 판단하고 탐색 범위를 반으로 줄이는 것을 반복하여 데이터를 찾는 방법

비교를 수행할 때마다 탐색 범위가 절반으로 줄어들어 매우 효율적이나 반드시 데이터가 정렬되어 있어야한다.

 

 

시간 복잡도: O(logn)

 

 

색인 순차 탐색(Indexed Sequential Search)

인덱스 테이블을 사용하여 탐색의 효율을 높이는 방법

 

 

보간 탐색(Interpolation Search)

탐색키가 존재할 위치를 예측하여 탐색하는 방법