검색

컴퓨터 과학에서 검색이란 아이템의 집합 중에서 특정한 속성을 가진 한 아이템을 찾는 과정.
그래서 검색은 핵심적인 컴퓨터 과학 알고리즘 중 하나이다.
아이템의 수가 매우 많은 컴퓨터의 특성상 매우 효율적인 검색 알고리즘이 필요하게 된다.
또한 마찬가지로 아이템을 잘 정렬하는것도 검색 효율을 크게 향상시키는 요인이 된다. 그래서 정렬 알고리즘도 매우 중요하다.

정렬 알고리즘이 더 중요하지 않을까? 무순서 선형 검색 알고리즘이 아니라면 자료가 잘 정렬되어 있다는 가정 하에 실행되는 알고리즘들이니까.

주요한 검색 알고리즘들로는 다음과 같은 것들이 있다.

• 무순서 선형 검색 (Unordered Linear Search)
• 정렬/순서 선형 검색 (Sorted/Ordered Linear Search)
• 이진 검색 (Binary Search)
• 심볼 테이블 (Symbol Table)과 해싱(Hashing)
• 문자열 검색 알고리즘 : 트라이(Trie), 삼진 검색 (Ternary Search)와 접미 트리(Suffix tree)

무순서 선형 검색

무작위로 저장된 데이터들을 처음부터 순회하면서 조건에 맞는 항목을 검색한다.
시간 복잡도는 모든 배열을 순회해야 하기 때문에 O(n).

정렬/순서 선형 검색

자료가 정렬되어 있기 때문에 마찬가지로 O(n) 복잡도를 가진다고 하더라도 조금 더 빨리 끝날 수 있다.

이진 검색

이진 검색 트리 시간에 배웠던대로 계속해서 탐색 범위를 반으로 줄여나가기 때문에 O(logn)의 복잡도를 가진다.
노드를 검색하는 횟수는 트리의 높이보다 많을 수 없는데, 트리의 높이가 logn이다.