[Python 으로 배우는 알고리즘] 이분탐색(Binary Search)

느린 개발자·2021년 1월 4일

Algorithm

목록 보기

1/2

📌 Introduction

어떤 배열에서 원하는 원소를 찾고자 한다면 어떻게 해야할까? 아마도 가장 간단한 방법은 배열의 첫 원소 부터 모든 원소를 검색하는 선형탐색 일 것이다. 선형탐색은 $O(N)$ 의 시간복잡도를 가지는데, 배열이 크고 검색이 자주 일어 난다면 결코 짧은 시간이 아닐 것이다. 하지만 배열의 원소가 정렬 되어 있지 않고, 정렬할 수도 없다면, 이 방법은 확실하게 원하는 원소를 찾을 수 있는 방법이다. 그렇지만, 만약 정렬할 수 있는 상황 이라면 더 좋은 방법은 없을까?

이분탐색 은 탐색 기법 중 하나로 정렬되어 있는 데이터 를 두 부분으로 분할해서 찾는 분할정복(Divide & Conquer) 이다. 구체적인 알고리즘은 다음과 같다.(오름차순 정렬 기준으로 설명)

탐색하고자 하는 데이터는 정렬 되어 있다.
배열의 양 끝인 left, right 를 이용하여 mid 를 찾는다.
mid 의 값과 찾고자 하는 target 을 비교한다.
3-1. mid 의 값보다 target 이 큰 경우 left=mid+1 로 옮기고 오른쪽을 탐색한다.
3-2. mid 의 값보다 target 이 작은 경우 right=mid-1 로 옮기고 왼쪽을 탐색한다.
left<=right 인 동안 2~3번 과정을 반복한다.

💡 Time complexity

이분탐색의 시간복잡도는 다음과 같은 이유로 $O(logN)$ 이다.

📃 Proof

📝 Implementation

❓ Question

이분탐색은 중복이 있는 데이터에서 target의 존재성을 확인하는 작업에는 문제가 없지만, 중복의 시작과 끝의 정확한 위치를 요구하는 작업에는 문제가 생긴다.

❗ Answer

이분탐색 + lower bound + upper bound 를 통해 시작과 끝의 정확한 위치를 확인할 수 있다.

lower bound : target 보다 같거나 큰 값 중 가장 앞에 있는 원소의 위치.
upper bound : target 보다 큰 값 중 가장 앞에 있는 원소의 위치.

위의 그림을 보면 찾고자 하는 값이 3인 경우 lowerbound(3) 은 3보다 크거나 같은 원소 중 가장 앞에 있는 원소의 위치 3 , upperbound(3) 은 3보다 큰 원소중 가장 앞에 있는 원소의 위치 6 을 리턴한다.

아래는 발생할 수 있는 여러가지 케이스를 보여준다.

주목해야 할 부분은 모든 데이터가 target 보다 작을 경우 데이터 범위 밖의 값을 리턴해야 하기 때문에 일반적인 이분탐색과 달리 right 는 len(array)-1 이 아닌 len(array) 가 된다.
또한, target을 찾았을때 끝내는 것이 아닌 left/right 를 조절해서 범위를 찾는다.