탐색이란?

컴퓨터 프로그램에서 탐색은 하나 이상의 필드(field)로 구성되는 레코드(record)의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이러한 레코드들의 집합을 테이블(table)이라 부른다. 레코드들은 서로 중복되지 않고 고유한 값을 가지는 키를 가지는데, 이것을 탐색키(search key)라 부른다.

맵이란?

맵은 탐색을 위한 자료구조이다. 맵(map) 또는 사전(dictionary)은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조를 말한다. 맵은 키를 가진 레코드(keyed record) 또는 엔트리(entry)라 불리는 키-값 쌍(key, value)을 테이블에 저장한다. 이때 각 키는 유일하고 맵에 저장되는 키와 값은 어떠한 자료형도 가능하다.

키를 가진 레코드의 추상 자료형은 다음과 같다.

맵의 추상 자료형은 다음과 같다.

맵을 구현하는 가장 간단한 방법은 배열일 것이다. 그러나 맵의 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 보다 효율적인 자료구조를 사용해야 한다.

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

순차 탐색

만약 배열을 이용해 맵을 구현하고 배열을 정렬하지 않으면 순차 탐색 방법을 사용할 수 있다. 순차 탐색(sequential search)은 가장 간단하고 직접적인 탐색 방법이다. 순차 탐색은 정렬되지 않은 배열에서 탐색키를 찾을 수 있는데, 배열의 요소들을 처음부터 마지막까지 하나씩 검사하여 원하는 레코드를 찾는 방법이다. 순차 탐색의 시간 복잡도는 $O(n)$이 된다.

Untitled

정렬된 배열에서의 탐색

정렬된 배열에서의 개선된 순차 탐색

정렬된 리스트를 순차 탐색할 경우 비교 횟수는 배열에 해당 항목이 존재하여 탐색이 성공했을 경우에는 일반 순차 탐색과 동일하지만, 해당 항목이 리스트에 존재하지 않아서 탐색이 실패할 경우에는 비교 횟수가 반으로 줄어든다. 그러나 시간 복잡도의 차수는 원래 순차 탐색과 동일하게 O(n)으로 변함이 없다.

정렬된 배열에서의 이진 탐색

정렬된 배열의 탐색에는 이진 탐색(binary search)이 적용될 수 있다. 이 방법은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 부분 배열에 있는지 오른쪽 부분 배열에 있는지를 판단하고 다음 단계의 탐색 범위를 반으로 줄인다. 따라서 매 단계에서 검색해야 할 리스트의 크기가 반으로 줄어든다.