[Python] BOJ/백준 1920번 수 찾기

[문제]

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

1920번: 수 찾기

 

[풀이]

두 번째 코드로 먼저 풀었는데 재귀로 압축할 수 있을 것 같아서 재귀로도 풀어봤다.

 

1. 먼저 리스트 a를 정렬시킨다.

2. 왼쪽과 오른쪽 인덱스를 지정한다.

3. 왼쪽, 오른쪽 인덱스 값을 이용해 중간 지점 인덱스를 구한다.

4. 중간 지점의 값과 찾고자하는 값을 비교한다.

   1) 중간 지점 값이 찾는 값보다 클 경우 -> 오른쪽 값을 mid-1로 지정

   2) 중간 지점 값이 찾는 값보다 작을 경우 -> 왼쪽 값을 mid+1로 지정

   3) 중간 지점 값과 찾는 값이 일치할 경우 -> return 1

 

[코드]

- 첫 번째 코드 (이분 검색 + 재귀)

def binary_search(i, a, left, right):
    if left > right:
        return 0
    mid = (left + right) // 2
    if a[mid] > i:
        return binary_search(i, a, left, mid-1)
    elif a[mid] < i:
        return binary_search(i, a, mid+1, right)
    else:
        return 1


if __name__ == '__main__':
    n = int(input())
    a = sorted(list(map(int, input().split())))
    m = int(input())
    b = list(map(int, input().split()))

    for i in b:
        left = 0
        right = n - 1
        print(binary_search(i, a, left, right))

 

- 두 번째 코드 (이분 검색)

if __name__ == '__main__':
    n = int(input())
    a = sorted(list(map(int, input().split())))
    m = int(input())
    b = list(map(int, input().split()))

    left, right = 0, n-1
    for i in b:
        left, right = 0, n - 1
        flag = False
        while(left <= right):
            mid = (left + right) // 2
            if a[mid] > i:
                right = mid - 1
            elif a[mid] < i:
                left = mid + 1
            else:
                flag = True
                break
        if flag:
            print("1")
        else:
            print("0")