수 찾기

스타트 택시를 오늘 내로 풀고 포스팅 하는게 목표였지만, 끝내 풀지 못해서 가벼운 이분탐색 문제를 가져왔다.😢

문제분석

정말 말 그대로 이분탐색이다.

[1, 3, 4, 5, 7, 8, 9, 11, 12]에서 이분 탐색으로 4를 찾는 과정에 대해 그림을 그려봤다.(이분 탐색을 할 때 리스트는 정렬된 상태여야 한다!)

• 초기에 양끝 포인터는 0번째와 8번째 요소를 가리키고 있다. 이제 그 가운데인 4번째 요소를 살펴보자. 4번째 요소는 7로 4보다 크다. 따라서 4는 0~3중에 있다고 생각할 수 있다.

• 위의 과정을 반복해보자. 0과 3의 가운데인 1(=(0+3)//2)을 살펴보면, 1번째 요소는 3으로 4보다 작다. 따라서 4는 2~3중에 있다.

• 2와 3의 가운데인 2를 살펴보자. 2번째 요소는 4로 우리가 찾고있는 수와 일치한다!

순차탐색을 활용하면 시간복잡도가 0(n)이고, 이분탐색을 통해 원소를 탐색하면, O(logN)내에 탐색할 수 있다. 이분탐색은 리스트가 정렬되어 있는 상태에서만 쓸 수 있다는 점에 유의하자.

CODE

import sys
read = sys.stdin.readline

n = int(read())
A = list(map(int, read().split()))
A.sort()
m = int(read())
num = list(map(int, read().split()))

def binsearch(x):
    if x > A[-1] or x < A[0]:
        return 0
    if x == A[-1] or x == A[0]:
        return 1
    l, r = 0, n-1
    while l <= r:
        mid = (l+r)//2
        if A[mid] == x:
            return 1
        elif A[mid] < x:
            l = mid+1
        else:
            r = mid-1
    return 0

    # 이렇게 while문 다 돌고 나서도 x를 찾지 못한 경우에
    # 0을 return해줘야 하는데 이걸 생각못했었다.
for i in num:
    print(binsearch(i))

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]