[Binary Search] 이진 탐색

[Binary Search] 이진 탐색

이진 탐색 Binary Search (이분 탐색이라고도 한다.)

이진 탐색은 순차 탐색과 달리 모든 경우를 다 탐색하지 않습니다.

이진 탐색이란 한번 비교를 거칠 때 탐색 범위를 반으로 줄여가며 탐색을 하는 방법입니다.

따라서 이진 탐색의 시간 복잡도는 O(logN)입니다.

이진 탐색의 경우 조건은 앞으로의 탐색 과정을 보면 알겠지만, 값이 정렬되어 있어야 한다는 것이다.

배열에 값이 저장되어 있던, 어떤 특정한 값을 찾던지 간에 탐색해 가는 과정에서 범위를 줄이기 위해서는 

정렬을 통해 더이상의 가능성이 존재하지 않는다는 보장이 되어 있어야 하기 때문이다.

이진 탐색의 탐색 과정

2

4

5

7

9

10

12

15

21

25

위와 같이 정렬된 배열에서 이진 탐색 알고리즘을 적용하여 데이터 12를 탐색해 보도록 하자.

우선 첫번째로 데이터 집합의 중앙 요소를 선택하여 비교를 한다.

2

4

5

7

9

10

12

15

21

25

중앙 요소가 원하는 데이터보다 작으므로 원하는 데이터는 중앙보다 오른편에 위치해 있을 것입니다.

따라서 범위를 중앙부터 끝으로 두어 다시 탐색을 합니다.

수정한 범위의 중앙 요소를 찾습니다.

2

4

5

7

9

10

12

15

21

25

중앙 요소 15는 찾는 데이터 12보다 크므포 중앙보다 왼편에 답이 위치해 있습니다.

2

4

5

7

9

10

12

15

21

25

중앙요소 10은 원하는 데이터 12보다 작으므로 데이터는 중앙 오른편에 위치해 있을 것입니다.

2

4

5

7

9

10

12

15

21

25

중앙 요소 12는 원하는 데이터 12와 같으므로 답을 찾았습니다.

(또는 답이 배열에 존재하지 않고 가장 근접한 작은 또는 큰 데이터를 찾는 경우 

탐색의 종료 조건은 데이터의 존재 여부가 아닌, 탐색 범위를 기준으로 두면 됩니다.)

또한, 특정 값을 찾는 것 이외에 정답을 구하는 문제에서 이진 탐색을 이용할 수 있다.

이진 탐색을 이용하여 답을 구하는 것의 핵심은 X가 가능한지 아닌지의 여부를 판단하는 것이다.

예를 들어, 정답을 구하는 문제로는 A에서 B까지 가는 가장 빠른 시간을 구하는 것이 문제라면

'A에서 B까지 X라는 시간으로 이동할 수 있나?' 의 여부를 가지고 탐색을 해 나가야 한다.

A에서 B까지 가는 가장 빠른 시간이 M인 경우

* M보다 빠른 시간은 모두 불가능

* M보다 큰 시간은 모두 가능

이렇게 나눌 수 있다.

A -> B 1이라는 시간으로 이동할 수 있나? => NO

A -> B 2이라는 시간으로 이동할 수 있나? => NO

A -> B 3이라는 시간으로 이동할 수 있나? => NO

A -> B 4이라는 시간으로 이동할 수 있나? => YES

A -> B 5이라는 시간으로 이동할 수 있나? => YES

이러한 과정을 거쳐 M = 4의 시간이 가장 빠른 시간이라는 답을 구할 수 있다.

다시 결론을 내자면

* 어떤 기준 X를 가지고 Yes / No 로 나누어지는 것만 정답을 찾을 수 있다.

이진 탐색 관련 문제 :

랜선 자르기    

나무 자르기

공유기 설치

[참고] http://blog.eairship.kr/246