탐색 알고리즘 - 이진 탐색

1. 이진 탐색(Binary Search)의 기본 개념

2. 이진 탐색의 손코드 구현

3. 이진 탐색의 코드 구현

4. 문제 풀이 해답

 

 

1. 이진 탐색(Binary Search)의 기본 개념

 

(1) 이진 탐색의 개념

 

이진 탐색은 쉽게 말해서 원하는 데이터를 찾을 때 "중간을 기준으로 찾는 것"입니다. 중간에 없으면 다시 왼쪽 오른쪽을 나누어서, 거기서 또 중간 지점을 들여다 보는 방법입니다. 

 

그냥 개념적으로 보면 이게 무슨 뻘짓인가 싶기도 하지만, 탐색 문제에서 시공간 복잡도를 굉장히 절약해줄 수 있는 강력한 Tool될 수도 있습니다. 

 

(2) 예시를 통한 코테 대비 - 병뚜껑 찾기 - 출처: www.fun-coding.org

잔재미코딩 온라인 강의 사이트입니다

 

문제 상황

 

자 이 문제를 아래의 코드 구현을 통해서 해결할 것입니다. 해답을 원하시는 분들은 끝까지 봐주세요~!!

 

 

 

(2) 이진 탐색의 특성

 1) 분할 정복 (Divide Conquer)

  - Divide: 문제를 한 번에 해결할 수 없다면, 문제를 나누어서 접근한다. 

  - Conquer: 나누어진 문제가 충분히 작거나, 해결이 가능하면 해결한다. 그렇지 못 하다면 계속 Divide를 해서 문제를 나눈다. 

 

여기서는 문제를 계속 "중간"을 기준으로 나눈다는 관점에서 Divide의 특성이 있고, 찾고 있는 데이터를 찾았다면 멈춘다는 점에서 Conquer의 특성을 보이고 있는 탐색 알고리즘입니다.  

 

 2) 재귀함수 

 재귀함수의 특징은 함수 내에서 자기 자신을 다시 불러오는 구조의 함수를 의미합니다. 

 

 문제를 Divide할 때, 계속 자기 자신의 함수를 써서 나누는 특징이 있기에 재귀함수를 통해 쉽게 구현할 수 있습니다. 

 

 따라서 재귀함수를 모르시는 분들은 기본 개념을 다시 잡고 오시면 이해를 빨리 하실 수 있습니다. 

 (재귀함수 기본 개념 설명 포스팅)

 

 

 3) 이진 탐색 VS 순차 탐색의 효율성 비교  

 가지고 있는 데이터를 100% 모른다면, 순차 탐색은 최악의 경우 모든 인자를 비교하고 탐색해야 할 수도 있습니다.

 

이에 반해 이진 탐색은 알고리즘 구성상 Conquer의 조건이 들어있기 때문에 시공간 복잡도를 반으로 절약해줄 수 있는 강점이 있습니다. 

 

아래의 사진을 통해서 한 번 보시죠. 

 

 

보시다시피 순차 탐색은 굉장한 리스크를 포함하고 있는 함수인 것을 볼 수 있습니다. 

 

 

2. 손코드의 구현 

 

def 이진탐색(데이터, 원하는 데이터)

 

## 데이터가 한개만 있을 때 / 멈추는 케이스 설정

멈추는 경우1. 데이터가 1개인데, 찾는 데이터일 경우

멈추는 경우2. 데이터가 1개인데, 찾는 데이터가 없는 경우

멈추는 경우3. 데이터가 더 이상 없는 경우

 

## 데이터가 여러 개 있는 경우

데이터의 반 선언 = medium

if 데이터의 중간(medium) == 찾는 데이터 -> 멈춤 (Conquer)

else:

   데이터의 중간 > 찾는 데이터 -> 오른쪽에서 이진 탐색 실행 (재귀함수로 Divide)

   데이터의 중간  < 찾는 데이터 ->왼쪽에서 이진 탐색 실행    (재귀함수로 Divide)

 

3. 이진탐색의 코드 구현

 

def b_search(data, search):
    
    if len(data) == 1 and data[0] == search:
        return '찾았다. {}'.format(search)
    if len(data) == 1 and data[0] != search:
        return '응 없어~'
    if len(data) == 0:
        return '응 한 개도 없어 ~'
    
    medium = len(data) // 2 
    if search == data[medium]:
        return '찾았다.{}'.format(search)
    
    else:
        if search > data[medium]  :
            return b_search(data[medium+1:], search)
        else:
            return b_search(data[:medium], search)

 

 

4. 문제 풀이 해답 

 

문제 풀이의 해답