탐색1 : 선형탐색, 이진탐색

탐색의 분류

1. 선형 자료구조 ( 어레이, 리스트, ...) 내에서의 탐색

• 선형탐색 (linear search) 또는 순차탐색 (sequential search) 
• 이분탐색 (binary search) : 분할정복을 이용한 탐색
• 해싱 (hashing)

 

2. 비선형 자료구조 ( 트리, 그래프, ...) 내에서의 탐색

• tree traversal
• DFS
• BFS

 

선형탐색, linear Search

• 정의 : 데이터의 집합을 처음부터 끝까지 차례대로 하나씩 검색하는 방법
• 장점 : 구현하기 쉽고 데이터 집합이 정렬되어 있지 않아도 된다
• 단점 : 검색시간이 오래걸린다
• 시간복잡도
  • worst : O(n)
  • average : O(n)
  • best : O(1)     // 첫번째 인덱스의 값이 찾고자 하는 값인 경우

 

이분탐색, Binary Search

• 정의 : 데이터 집합의 범위를 반씩 나누어 가면서 분할정복하여 탐색하는 방법
• 장점 : 탐색 속도가 빠르다
• 단점 : 데이터집합 안의 값들이 정렬되어 있어야 한다.
• 시간복잡도 
  • worst : O(logn)
  • average : O(logn)
  • best : O(1)      // 중간 인덱스의 값이 찾고자 하는 값인 경우