[코스모스 4주차] 이분 탐색 알고리즘

"import sys"

sys = system, stdin = standard input, readline = 한 줄씩 입력받기

 

input

: 무조건 문자열로 입력받음 정수를 입력해도 따로 int(input()) 해 줘야 함

 

→ input 함수는 매 호출마다 한 줄씩 읽고 문자열로 반환하는데, sys.stdin.readline()은 개행 문자를 포함한 한 줄을 읽고 문자열로 반환하여 대규모 입력 처리 시 효율적임

 

이분 탐색 (Binary Search)이란

`

내 코드

import sys # system specific parameters and functions -> 파이썬 인터프리터를 제어할 수 있는 방법 제공

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort() # 이분 탐색은 정렬된 상태에서만 사용!

m = int(sys.stdin.readline())
muns = list(map(int, sys.stdin.readline().split()))

for i in muns:
    l, r = 0, n - 1
    gotit = False # 해당 수가 존재하는지에 대한 여부

    while l <= r: # left가 right보다 작을 때만 루프 안을 돌음
        m = (l + r) // 2 # 중간 지점 지정
        if i == nums[m]:
            print(1)
            gotit = True
            break
        elif i > nums[m]:
            l = m + 1
        else:
            r = m - 1
    if gotit == False:
        print(0)