2. Search(선형 검색 & 이진 검색)

알고리즘 및 자료 구조 정리 두 번째는 검색방법이다. 두 가지의 검색 방법을 제시하는데, 선형 검색과 이진 검색이다.

 

1. 선형 검색

- 요소가 직선 모양으로 늘어선 배열에서의 검색으로 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 알고리즘

 

arr 배열에서의 모습을 보면

 

arr 배열

6

4

3

2

1

3

8

에서 처음 부터 순서대로 검색하여 원하는 수가 있으면, 검색 성공!! 아니면, 검색 실패!!

 

이러한 예시를 통해서 while문과 for문으로 각각 선언한 선형 검색법을 알아 볼 수 있다.

위 예시에서 제시한 선형 검색법은 종료 조건을 만족하기 위해 두 가지의 조건을 체크해야한다.

• 검색값을 발견하지 못 하고 배열의 끝을 지나간 경우
• 검색할 값과 같은 요소를 발견한 경우

이렇게 두 가지의 조건을 찾으면서 종료 조건을 검사하는 비용이 두 배로 들게 되는데 이러한 점을 효율적으로 줄여 주기 위해 보초법이라는 방법을 사용한다.

 

**보초법 : 마지막 값을 초반에 정해두고, 그 index 값을 찾게 되면 실패라고 지정해주어서 종료 조건을 검사하는 비용을 절반으로 줄여주는 방법.

 

보초법을 사용하여 search 함수를 다시 구현해 주었다. a[n] = key로 마지막 자리에 미리 보초를 추가해 놓고, i가 n 이라면 -1을 출력하여 검색 실패를 나타내어 주는 방식이다.

 

 

2. 이진 검색

- 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘으로 업다운 게임을 생각하면 된다. 알고리즘 문제풀이에서도 한번 구현했던 적이 있는 방식으로 절반을 정해두고, 위 아래의 숫자로 구역을 반으로 줄여가는 방식이다. 선형 검색법 보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.

(List 카테고리의 배열과 List를 활용한 수 찾기 참고)

 

 

이진 검색으로 구현한 예시이다. 맨 앞을 pl 0, 맨 뒤를 pr n-1로 지정해 주고 pc가 절반을 나타낼 수 있도록 해 주었다. pl <= pr 이 아닐 경우는 검색에 실패한 것으로 간주한다.

 

여기서 가장 주의해야 할 점은 main 함수 안에서 오름차순으로 입력받는 부분이다. 이진 검색은 오름차순과 내림차순을 전제로 하고 검색하는 방식이므로 오름차순 or 내림차순으로만 입력받아야 한다.

 

 

**복잡도 : 알고리즘의 성능을 객관적으로 평가하는 기준

• 시간 복잡도 : 실행에 필요한 시간을 평가
• 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가

 

1. 선형 검색의 시간 복잡도

 

위 search1 함수에서의 시간복잡도를 계산해 보면

5번째 줄 - O(1)

6번째 줄 - O(n)

7번째 줄 - O(n)

8번째 줄 - O(1)

10번째 줄 - O(n)

11번째 줄 - O(1)

13번째 줄 - O(n)

 

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) + O(n) = O(max(1, n, n, 1, n, 1, n)) = O(n)

=> 전체 복잡도는 차원이 가장 높은 복잡도를 선택함

결론적으로 O(n)이 선형 검색법의 시간 복잡도가 된다.

 

 

3. 이진 검색의 시간 복잡도

 

위 bin_search 함수에서의 시간 복잡도를 계산해 보면,

 

5 - O(1)

6 - O(1)

10 - O(log n)

11 - O(log n)

12 - O(1)

14 - O(log n)

15 - O(log n)

17 - O(log n)

18 - O(log n)

20 - O(log n)

22 - O(1)

 

O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) + O(log n) + O(log n) + O(log n) + O(log n) + O(1)

= O(log n)

 

결론적으로 O(log n)가 이진 검색법의 시간 복잡도가 된다.

 

O(n) > O(log n) 이므로 여기서 선형 검색의 시간 복잡도가 이진 검색의 시간 복잡도 보다 더 큰 것을 알 수 있다.