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

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

Algorithm

목록 보기
1/2

📌 Introduction

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

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

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


💡 Time complexity

이분탐색의 시간복잡도는 다음과 같은 이유로 O(logN)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 보다 작을 경우 데이터 범위 밖의 값을 리턴해야 하기 때문에 일반적인 이분탐색과 달리 rightlen(array)-1 이 아닌 len(array) 가 된다.
    또한, target을 찾았을때 끝내는 것이 아닌 left/right 를 조절해서 범위를 찾는다.

📝 Implementation of lower bound

📝 Implementation of upper bound


📚Reference

The figure for header # Introduction
The figures for header ## Answer

profile
남들보단 느리지만, 끝을 향해

0개의 댓글