[백준/Python] 1920번: 수 찾기(이분 탐색)

1. 문제

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

1920번: 수 찾기

 

2. 풀이 

⏰ 시간 초과 : 단순하게 생각해서 if문과 in을 사용하여 확인하였다. 역시나 시간 초과 .. 

✔️ 이분 탐색 : 시간초과가 나지 않게 빨리 찾을 수 있는 것은 역시나 '이분탐색'이다 ! 

 

3. 코드 

# 1920
def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start<= end :
        mid = (start + end) //2
        if data[mid] == target:
            return 1
        elif data[mid] < target:
            start = mid+1
        else:
            end = mid -1

    return 0


n = int(input())
arr = list(map(int,input().split()))
arr.sort()
m = int(input())
find = list(map(int,input().split()))



for f in find:
    isIn = binary_search(f,arr)
    print(isIn)

 

 

잊지말자 이분탐색 알고리즘 !! 

def binary_search(target, data):
    # data가 sort되어 있다고 가정 
    start, end = 0, len(data)-1 # index값 
    while start<= end: # start가 end를 넘지 않게 ! 
        mid = (start + end)// 2
        if data[mid] == target:
            return 1 # target이 있다면 1 반환
        elif data[mid] < target: # 찾고 있는 값보다 data[mid]값이 작을 때 
            start = mid+1 #start의 위치 큰 쪽으로 옮겨주기 
        else:
            end = mid-1 # end의 위치 작은 쪽으로 옮겨주기 
    return 0 # 다 돌았는데 target이 없다면 0반환