[알고리즘] 선형 검색과 이진 검색

검색의 종류

- 배열 검색

- 연결 리스트 검색

- 트리 검색

 

1. 선형 검색 (linear search/ sequential search)

 특징: 무작위로 늘어놓은 데이터 집합에서 검색

 쉽게 말해 배열의 전체 요소를 모두 탐색하는 것을 뜻한다.

 - 보초법: 선형검색의 비용을 줄이는 방법. 반복을 종료하는 판단 횟수를 줄이는 역할을 하는 것이 보초.

시간 복잡도: O(n)

 

2. 이진 검색(binary search) (분할정복법(divde and conquer 중 하나)

 특징: 일정한 규칙으로 늘어놓은 데이터 집합에서 검색, 즉 시퀀스가 정렬(sort)되어있어야함.

 중간 값과 찾으려는 값의 대소비교를 통해 범위를 절반씩 줄여 나감.

시간복잡도: O(logn)

 길이가 n인 배열을 이진 탐색하면 n, n/2, n/4, n/8, ...,  1회 실행될 것이다. 즉, 실행된 탐색 횟수를 k번이라고한다면,

 2^k = n

 k = log2n

 이 된다.