[백준 1920 파이썬] 수 찾기 (실버4, 이분 탐색)

알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/1920

SOLVE 1

분할 정복 풀이(재귀 이용)

import sys
input = sys.stdin.readline

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
B = list(map(int, input().split()))

def binarySearch(arr, target, start, end):
    if start > end:
        return 0
    
    mid = (start + end) // 2
    if arr[mid] < target:
        return binarySearch(arr, target, mid+1, end)
    elif arr[mid] > target:
        return binarySearch(arr, target, start, mid-1)
    else:
        return 1

for target in B:
    print(binarySearch(A, target, 0, len(A)-1))

SOLVE 2

for문 풀이

import sys
input = sys.stdin.readline

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
B = list(map(int, input().split()))

def binarySearch(arr, target):
    start, end = 0, len(arr)-1
    
    while start <= end:
        mid = (start + end) // 2
        
        if arr[mid] < target:
            start = mid+1
        elif arr[mid] > target:
            end = mid-1
        else:
            return 1
    
    return 0

for target in B:
    print(binarySearch(A, target))

풀이 요약

1. 이분 탐색 알고리즘 그 자체인 문제이다. (탐색할 리스트는 반드시 정렬된 상태여야 함을 유의)

2. 분할 정복으로 푸는 방법, for문으로 푸는 방법 둘 다 거의 유사하다.

3. 핵심 원리는 start=0, end=len(arr)-1 , 끝과 끝에서 시작해서, mid = (start+end)//2로 설정하고,

   arr[mid]와 target의 위치 관계에 따라, 만약 mid의 arr값이 target보다 작다면, mid 왼쪽의 arr부분은 탐색할 필요가 없다. arr은 정렬된 상태이기 때문이다. 이 때는 start = mid+1로 갱신해주고, 재귀로 같은 연산을 반복해준다.

배운 점, 어려웠던 점

• 이분 탐색 알고리즘에 대해 배웠다.