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

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

1920번: 수 찾기

 

<문제 요약>

  - 문제에서 주어진 N이 10만이다. 따라서 시간 복잡도가 O(n*n)이면 시간초과가 발생한다.

  - 이를 해결하기 위해 이분 탐색을 이용했다.

  - N개의 숫자 리스트와 M개의 숫자 리스트가 주어지고, M의 원소가 N에 있는지 확인하는 문제

 

<내 코드>

- binary_search(arr, target) 함수

  ## arr 리스트가 정렬되어 있어야함

  - arr : 탐색해야하는 리스트(문제에서는 N 리스트), target은 확인 대상(문제에선 M의 각 원소)

  - 이분 탐색의 start = 0, end = n -1로 설정, arr의 인덱스이다.

  - while문을 통해 반복

    - mid 는 start와 end의 중간으로 설정

    - 만약 arr[mid] == target 이면 원소를 찾았으므로 return 1

    - arr[mid]가 target보다 큰 경우 그 뒤의 범위에는 없으므로 end를 mid -1로 줄여준다.

    - arr[mid]가 target보다 작은 경우 그 앞의 범위에는 찾는 수가 없으므로 start를 mid + 1로 늘려준다.

 

- M리스트를 돌면서 확인

 

import sys
input = sys.stdin.readline

n = int(input())
N = list(map(int, input().split()))
N.sort()
m = int(input())
M = list(map(int, input().split()))

def binary_search(arr, target):
    start = 0
    end = n - 1

    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return 1
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

    return 0

for i in range(m):
    print(binary_search(N, M[i]))