[이분탐색 / python] 백준 1920. 수 찾기

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

1920번: 수 찾기

 

문제 해석

쉬운 이분탐색 문제이다. 만약 단순히 for loop과 in 연산자를 이용해서 탐색하려 한다면, 그 시간복잡도가 O(n^2)이고 M의 개수가 100,000이므로 1초는 가볍게 넘길 것이다. 따라서 단순히 모든 요소를 탐색하는 개념으로 접근해서는 안된다. 이러한 경우 절반씩 짤라서 탐색하는 이분탐색(Binary Search)를 이용하면 O(logN)까지 줄일 수 있으므로 시간 내에 탐색을 완료할 수 있다.

 

풀이

def binary_search(n, arr):
    left = 0
    right = len(arr)-1

    while left <= right:
        mid = int((left + right) / 2)
        if arr[mid] == n:
            return 1
        elif arr[mid] > n:
            right = mid - 1
        elif arr[mid] < n:
            left = mid + 1
    return 0
import sys
input = sys.stdin.readline

t = int(input())
li = sorted(list(map(int, input().split())))
q = int(input())
arr = list(map(int, input().split()))
for i in arr:
    print(binary_search(i, li))

 

* 이분탐색 vs 투포인터

- 이분탐색은 양 끝(left, right)의 중간값(mid)을 이용하여 매번 연산 범위를 반으로 줄여나가며 탐색하는 알고리즘이다.

- 투포인터는 두 개의 포인터(left, right)를 한 칸씩 이동시키면서 원하는 값을 탐색하는 알고리즘이다. 이 알고리즘은 슬라이딩 윈도우 기법으로도 활용이 가능하다.

	Binary Search	Two Pointer
Time Complex	O(log N)	O(N)
given	list must be sorted	-