[개념] 이분탐색 (Binary Search)

이분탐색이란?

보통 간단하게 배열을 탐색하고자 한다면 선형탐색 (Linear Search)를 많이 사용하곤 한다.

하지만 배열의 길이가 굉장히 길거나 배열을 여러번 탐색해야한다면 선형탐색은 매우 느리다.

 

선형탐색보다 탐색시간을 조금더 줄일 수 있는 것이 바로 이분탐색 (Binary Search) 이다.

이분탐색은 탐색할 배열의 중간의 값을 확인하여 탐색 범위를 절반씩 줄여나가며 탐색하는 알고리즘이다.

 

예를들어, [1,3,5,7,9] 인 배열에서 7을 찾는다고 하면

check 함수를 다음과 같이 설정하고 [check() = 7보다 크거나 같은 수이면 True, 그렇지 않으면 False]

배열의 중간값인 5를 먼저 확인한다.

check(5) = False 이므로 5보다 배열 왼쪽에 있는 1, 3은 확인하지 않는다.

[5,7,9]에서 다시 탐색을 시작하여 7을 찾아내는 방식이다.

 

예시를 통해 알 수 있지만 이분탐색은 탐색대상이 순차적으로 정렬되어 있지 않으면 쓸 수 없다.

기준이 되는 값보다 큰 쪽 혹은 작은쪽이 탐색대상이 아니라는 것을 확신할 수 있어야 하기 때문이다.

다만 정렬이 오름차순인지 내림차순인지와는 관계없이 사용할 수 있다.

 

구현 Tip

이분탐색을 구현할 때의 가장 큰 어려움은 탐색의 범위를 지정하고 결과값을 특정하는 것이 어렵다는 것이다.

탐색의 범위를 [start, end] 라 하였을 때 알고리즘 문제마다 결과값을 찾는 구현이 미묘하게 달라질 수 있다.

 

그래서 아래와 같이 구현로직을 정해놓고 구현하면 조금 더 수월하게 구현할 수 있다.

 

1. 정답을 포함하도록 탐색범위 start, end 값을 잡고 mid = (start+end)/2로 설정한다.

2. check(start) == check(mid) 이면 start = mid, check(end) == check(mid) 이면 end = mid로 설정한다.

3. start+1 == end 를 만족하면 반복문을 탈출하고 start와 end 중 정답을 결정

 

위 구현 Tip은 구종만 저, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」 에서 참고하였습니다.