[python] 이분 탐색(Binary Search)_백준10815번, 10816

이분 탐색 = 이진탐색 (binary search)

탐색 범위를 두 부분으로 분할하면서 찾는 방식으로
처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지닌다.

시간복잡도
전체 탐색 : O(N)
이분 탐색 : O(logN)

진행 순서
1. 비교할 리스트를 정렬한다.
2. left와 right로 중간 값인 mid를 설정한다.
3. mid에 위치한 값과 내가 구하고자 하는 값을 비교한다.
4. 구할 값이 mid보다 높으면 : left = mid+1, 구할 값이 mid보다 낮으면 : right = mid - 1
5. left > right가 될 때까지 계속 반복한다.

숫자 카드 - 백준 10815

solution

첫번째 솔루션은 간단하게 두 배열을 생성한 후,
있는지 없는지 체크하는 로직이었다.

n = int(input())
array_n = input().split(' ')
m = int(input())
array_m = input().split(' ')

for i in array_m:
    if i in array_n:
        print(1, end = ' ')
    else:
        print(0, end = ' ')

배열의 크기가 너무 커지면, time limit 에 걸리는 문제가 발생한다. 그래서 순차 탐색이 아닌 이분 탐색의 방법으로 풀어야 한다.

# 비교할 대상인 array_n은 이분탐색을 위해 오름차순 정렬을 해준다.
n = int(input())
array_n = input().split(' ')
array_n.sort()
m = int(input())
array_m = input().split(' ')

# 이분 탐색 함수
def binary_search_m(start, end, m, array_n):
    while start <= end:
        # 중간 값을 계속 비교해가며 비교할 숫자의 후보를 절반씩 줄여간다.
        mid = (start+end)//2
        if array_n[mid] == m:
            # m 값을 찾을 경우
            return True
        elif array_n[mid] > m:
            end = mid - 1
        else:
            start = mid + 1
    # 못 찾고 while 문을 빠져나올 경우
    return False


for m in array_m:
    if binary_search_m(0, len(array_n)-1, m, array_n):
        print(1, end = ' ')
    else:
        print(0, end = ' ')

숫자카드2 - 백준 10816번

위 숫자카드 1번 문제에서 더 나아가 중복까지 고려해서 각각 숫자의 개수 찾는 문제이다.
처음에는 파이썬의 내장함수 count()를 활용해서 구현했으나, 개수가 많아지면 시간 초과가 뜨게 되었다.
리스트의 count 함수는 in 함수와 동일하게 array 전체를 탐색해야하므로, 시간복잡도 O(n)을 가진다.
비교할 요소가 m개라면 위의 방법으로 단순 구현한 알고리즘의 시간 복잡도는 mxn이 걸리게 되고, O(N2)이 된다.
여기서 이분탐색 요소를 활용하여 시간 초과를 해결해보자!

solution

n = int(input())
array_n = list(input().split(' '))
array_n.sort()
m = int(input())
array_m = list(input().split(' '))

# def binary_count(target, array_n):
#     start = 0
#     end = len(array_n) - 1
#     mid = (start + end) // 2
#     while start <= end:
#         if array_n[mid] < target:
#             start = mid + 1
#         elif array_n[mid] > target:
#             end = mid - 1
#         else:
#             target_array = array_n[start:end]
#             count_m = target_array.count(target)
#             return count_m
#     return 0

def binary(n, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if n == N[m]:
        return N[start:end+1].count(n)
    elif n < N[m]:
        return binary(n, N, start, m-1)
    else:
        return binary(n, N, m+1, end)

for target in array_m:    
    count_target = binary(target, array_n, 0, len(array_n)-1)
    print(count_target, end = ' ')