[백준 파이썬] 1920 수 찾기

📌문제 출처

백준 단계별 문제풀이 - 이분탐색
https://www.acmicpc.net/problem/1920

1920번: 수 찾기

❓ 문제

❗ 풀이

• 이분탐색 활용

📗 풀이 코드

import sys
input = sys.stdin.readline

def binary_search(q,n):
    sta,end = 0,n-1
    mid = (sta+end)//2
    while sta <= end:
        if nums[mid] == q: # 찾는 숫자를 발견했을 때
            flag = 1
            return 1
        if nums[mid] < q : # 찾는 숫자가 중간보다 뒤에 있을 때
            sta = mid+1
            mid = (sta+end)//2
        else : # 찾는 숫자가 중간보다 앞에 있을 때
            end = mid-1
            mid = (sta+end)//2
    return 0

n = int(input())
nums = sorted(list(map(int,input().split())))
_ = input()
questions = list(map(int,input().split()))

for q in questions:
    print(binary_search(q,n))

📗 코드 해설

• 정렬된 리스트에서 탐색하는 범위를 계속 반으로 줄여나간다.
• mid를 기점으로 이보다 큰 곳에 위치하면 mid+1
• end의 범위를, 작은 곳에 위치하면 sta
• mid-1의 범위를 탐색한다.
• sta=mid=end인 순간까지 탐색한다. 이 때 mid = 찾는 숫자이면 성공
• 위 순간까지도 찾는 숫자가 없다면 end가 sta보다 작아지기 때문에 탐색 종료