[알고리즘]알고리즘의 종류

선형탐색 알고리즘(Linear Search Algorithm)

:맨 처음부터 하나하나 살펴보는 알고리즘

 

예) 40이라는 숫자를 찾을 때

 

[1 3 8 11 12 13 19 21 31 34 40 49 53]

위와 같은 숫자열이 있을때 맨 왼쪽에 있는 ‘1’ 부터 시작 하여 3 8 11 12… 차례차례

확인을 하여 ‘40’ 이 나올때 까지 확인 작업을 반복한다.

40이 나오면 중단.

 

이진탐색 알고리즘(Binary Search Algorithm)

:중간값에 먼저 접근하여, 찾으려는 값과 중간값을 비교 후

중간값 기준 왼쪽 or 오른쪽을 선택하여 절반의 자료들을 확인하는 알고리즘

 

예)40 이라는 숫자를 찾을 때

 

[1 3 8 11 12 13 19 21 31 34 40 49 53]

 

1. 중간값을 찾는다. 위의 숫자열에서는 19가 중간값이 된다.
2. 중간값 인덱스 = (해당 범위의 양 끝의 인덱스값의 합) // 2
3. 40은 19보다 크므로, 19 기준 오른쪽에 자료가 있을것이라 추측 가능하다
4. 19의 오른쪽에 있는 자료들 중, 중간값을 찾는다
5. [1 3 8 11 12 13 19 21 31 34 40 49 53]
6. (해당 범위의 양 끝의 인덱스값의 합) // 2 를 하기 때문에 34가 중간값
7. 34 < 40 이므로 오른쪽 범위 선택!
8. [1 3 8 11 12 13 19 21 31 34 40 49 53]
9. 49 > 40 이므로, 왼쪽 범위 선택. 왼쪽 범위에 40만 남아있으므로

탐색 종료!

 

※주의점!

이진탐색은 정렬된 자료에만 사용 가능한 알고리즘이다!

 

이진탐색을 이용했을때, 5번의 과정으로 탐색이 종료되었고

선형탐색을 이용했을때, 11번의 과정으로 탐색이 종료되었다.

 

그때 그때 상황에 맞춰 어떤 탐색법이 좋은지 생각하여 코드를 작성하도록 하자!

만약 자료들이 정렬이 되어있지 않다면? -> 선형탐색

자료들이 정렬되어 있다면? -> 이진탐색