이분탐색 ( = 이진탐색 [ Binary Search ] )

이름에서 직관적으로 어떤 개념인지 알 수 있다. '이분 + 탐색'  

정렬되어있는 배열 혹은 특정 범위에서, 값을 찾는 강력한 도구로서 사용 될 수 있음. (선형탐색보다 유리하다!)

주된 목적은 탐색시 시간 복잡도상의 효율성을 높임에 있다. (평균 시간복잡도 NlogN )

*향후 응용범위에 대한 노하우가 깊어지면 글 수정을 통해 보완 예정.

개념

배열 혹은 특정 범위에서 찾고자하는 값이 있는 경우, 두 부분으로 나누어 탐색하고 가능성 없는 부분은 더 이상 탐색하지 않는다.

따라서 한번의 탐색당 탐색범위를 N/2로 줄여나갈 수 있다는 것이 장점이다.

이때, 두 부분으로 나누는 기준은 배열상 중앙에 위치한 값이다. (양 끝값의 평균값이 아님)  

   

이분탐색 사용의 전제조건은 배열이 반드시 미리 '정렬' 되어 있어야 한다는 것.

중앙값과 찾는 값의 대소 비교를 통해 나머지 반을 제외해야 하기 때문이다.

대소 비교하는 과정에서 중앙값과 찾는 값이 일치한다면 목적을 이뤘으므로 loop는 종료하게 된다.

 

예시)

아래에 N=10의 배열이 있다. 하기 배열에서 346이라는 값을 찾아보도록 하자.  (중앙값 / 찾는값)

아랫줄은 index이다. 찾는 범위를 index기준으로 지정한다면,

범위의 가장왼쪽의 index는 0 가장 오른쪽은 9 중앙값은 (0+9)//2 인 4로 생각할 수 있다.

left = 0   right =9  mid=4

3	5	10	23	58	99	143	256	346	756
0	1	2	3	4	5	6	7	8	9

중앙값 < 찾는값

---

배열이 정렬이 되어있기 때문에 찾는 값이 중앙값 기준 오른쪽에 있다는 것을 알 수 있다. 따라서 이전 배열의 중앙값 기준으로 좌측 배열들은 다음 탐색에서 제외한다. 새로운 탐색 범위에서 다시 중앙값의 index update.

 

left = 5  right = 9 mid = 4 

99	143	256	346	756
5	6	7	8	9

중앙값 < 찾는값

(만일 찾는 값이 756이 아닌 256이 었다면, 이번에 loop는 종료되었음) 

 

---

left = 8  right = 9 mid = 8 

346	756
8	9

중앙값 < 찾는값 이므로 마찬가지로 중앙값을 제외한 우측범위로 좁힌다. 

---

left = 9  right = 9 mid = 9 

756

9

mid값이 찾는값과 일치하게됨.

 

만일, 값 을 끝까지 못찾았다면 가장 근접한 index 값에서 loop가 종료하게됨. (초기 배열에 값 추가 후 정렬한다면 위치하게 될 index )

 

 

코드 예시) 백준 1920 수 찾기  [이분 탐색 기본 예제]

N=int(input()) 
A=list(map(int,input().split())) # A list
M=int(input()) 
M_list=list(map(int,input().split())) # M list
A.sort()

def binarysearch(arr,key:int):
    pl=0            #정렬된 배열에서 가장 왼쪽값의 index
    pr=len(arr)-1   #정렬된 배열에서 가장 오른쪽 값의 index 

    while True:
        pc=(pl+pr)//2    #배열의 중앙값의 index (while loop가 도는 동안 계속 update된다.)
        if arr[pc]==key:
            return 1     
        elif arr[pc]<key:
            pl=pc+1
        else:
            pr=pc-1
        if pl>pr:
            return 0
    
    
for i in M_list:
    print(binarysearch(A,i))