파이썬 / BOJ 백준 / 1920 수 찾기 - 이분 탐색

파이썬 / BOJ 백준 / 1920 수 찾기 - 이분 탐색

 

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

1920번: 수 찾기

 

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

 

문제 풀이

1. 이 문제는 이분 탐색 알고리즘을 이용하여 풀 수 있는 문제입니다.
(하나씩 순차적으로 찾게 되면 시간초과가 됩니다.)

2. 우선 입력된 배열 N을 정렬시킵니다.

3. 시작과 끝 지점을 각각 left와 right로 놓고, 중간 지점을 mid로 놓습니다.

4. mid에 위치한 값과 비교하여,
 4-1. 동일한 값이면, 1을 반환합니다.

 4-2. 값이 크면 left를 mid + 1로 놓고, 다시 검색합니다.

 4-3. 값이 작으면 right를 mid -1로 놓고, 다시 검색합니다.

 4-4. 원하는 값이 없으면, 즉 left 값이 right 값보다 크면 0을 반환합니다.

전체 코드

from sys import stdin

n = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
m = stdin.readline()
M = map(int, stdin.readline().split())

def binary(value, left, right):
    print(value, left, right)
    if left > right:
        return 0
    mid = (left+right)//2
    if value == N[mid]:
        return 1
    elif value < N[mid]:
        return binary(value, left, mid-1)
    else:
        return binary(value, mid+1, right)

for v in M:
    left = 0
    right = len(N)-1
    print("v 입니다.")
    print(binary(v,left,right))