[Python 알고리즘] Binary Search(이진탐색/이분탐색)

💡Python Binary Search (파이썬 이진 탐색)

이진탐색이란 '정렬된 자료'를 반으로 쪼개가며 원하는 값을 찾아가는 탐색 알고리즘이다.
반드시 정렬되어있는 배열에서만 탐색 가능하다. 시간복잡도는 O(logN)이다.

주로 left와 right 또는 low와 high 또는 start,end로 변수 이름을 쓴다.
가운데 지점(mid)을 찾고, 계속 left, right 값을 mid를 이용해 갱신하면서 범위를 좁혀나가는 알고리즘이다.

📌 알고리즘 전개과정

n개의 원소를 가지는 정렬된 배열 A가 있을 때, 찾으려는 값 K와 가운데 값을 비교했을 때,
K가 더 작다면 반드시 K는 A[0] ~ A[mid-1] 에 존재할 것이다.
K가 더 크다면 반드시 K는 A[mid+1] ~ A[n-1] 에 존재할 것이다.
K를 구할 때 까지 반복하면 구간이 점점 줄어들면서 마침내 A[mid]==K 일때, 탐색이 종료된다.
이 반복을 반복문을 통해 구현할 수 있고, 재귀를 통해 구현할 수도 있다.

📌 1. 비재귀적 알고리즘 (정방향)

#이분탐색 알고리즘 (정방향)
def BinarySearch(arr,target):
    #L: left, R: Right, M: Mid
    L,R = 0, len(arr)-1
    while(L <= R): # L>R 되면 탈출 (배열에 target이 없다)
        M = (L + R) // 2
        if(arr[M] == target): # target값에 해당하는 idx 찾음
            return M
        elif(arr[M] > target): # target 값보다 더 클 때
            R = M - 1 # R을 중간-1 의 idx로 갱신 
        else: #target 값보다 더 작을 때
            L = M + 1 # L을 중간+1 의 idx로 갱신
    return -1 #배열 내에 값이 없음

📌 2. 재귀적 알고리즘

#이분탐색 알고리즘 (재귀)
def BinarySearch(arr, target, left, right):
    if left > right: #배열 내에 값이 없음
        return -1
    mid = (left + right) // 2
    if arr[mid] > target: # target 값보다 더 클 때
    	#right 값을 mid-1로 대체하여 함수 호출
        return BinarySearch(arr, target, left, mid-1)
    if arr[mid] == target: # target 값에 해당하는 idx 찾음
        return mid
    if arr[mid] < target: # target 값보다 더 작을 때
    	#left 값을 mid+1로 대체하여 함수 호출
        return BinarySearch(arr, target, mid + 1, right)

📌 예시 문제: 백준 1920 파이썬

import sys

def BinarySearch(arr,target):
    #L: left, R: Right, M: Mid
    L,R = 0, len(arr)-1
    while(L <= R): # L>R 되면 탈출 (배열에 target이 없다)
        M = (L + R) // 2
        if(arr[M] == target): # target값에 해당하는 idx 찾음
            return M
        elif(arr[M] > target): # target 값보다 더 클 때
            R = M - 1 # R을 중간-1 의 idx로 갱신 
        else: #target 값보다 더 작을 때
            L = M + 1 # L을 중간+1 의 idx로 갱신
    return -1 #배열 내에 값이 없음

n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().rstrip().split()))
m=int(sys.stdin.readline())
b=list(map(int,sys.stdin.readline().rstrip().split()))
#사실 n,m값은 필요 없기 때문에 입력을 조금 더 간단하게 해결할 수 있다.

a=sorted(a)
for i in b:
    print(BinarySearch(a,i))