def Find(arr,target):
# 1번씩 다 비교하면서 출력해도 됨
# but 이진탐색으로 출력해보자
low = 0
high = N
mid = (high + low) // 2
while low < high:
# 이진탐색 시작, 중간값으로 대소비교
if arr[mid] > target:
high = high -1
mid = (high + low) // 2
elif arr[mid] < target:
low = low + 1
mid = (high + low) // 2
else:
# arr[mid] == target, 값을 찾음
return 1
#break point -> index를 벗어남. (찾는값이 없음)
if low > high:
return 0
# while 안에서 못찾았으면 무조건 not found.
return 0
N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))
for target in M_list:
# M_list[i]가 A에 있는지 없는지 찾는 함수, 있으면 1, 없으면 0 리턴
print(Find(A,target))
결과 : 시간 초과
def Find(arr,target,low,high):
if high < low:
return False
mid = (high + low) // 2
if arr[mid] > target:
return Find(arr,target,low,high-1)
elif arr[mid] < target:
return Find(arr,target,low+1,high)
else:
return True
N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))
for target in M_list:
# M_list[i]가 A에 있는지 없는지 찾는 함수, 있으면 True, 없으면 False 리턴
if Find(A,target,0,N-1):
print(1)
else:
print(0)
결과 : 런타임 에러
- 배열에 할당된 크기를 넘어서 접근했을 때
- 전역 배열의 크기가 메모리 제한을 초과할 때
- 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
- 0으로 나눌 떄
- 라이브러리에서 예외를 발생시켰을 때
- 재귀 호출이 너무 깊어질 때
- 이미 해제된 메모리를 또 참조할 때
- 프로그램(main 함수)이 0이 아닌 수를 반환했을 때
출처 : https://www.acmicpc.net/board/view/22980
수정사항 - Find함수 안에서 재귀로 호출할 때 index를 좀 더 효율적으로 주었다.
def Find(arr,target,low,high):
if high < low:
return False
mid = (high + low) // 2
if arr[mid] > target:
return Find(arr,target,low,mid-1)
elif arr[mid] < target:
return Find(arr,target,mid+1,high)
else:
return True
N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))
for target in M_list:
# M_list[i]가 A에 있는지 없는지 찾는 함수, 있으면 True, 없으면 False 리턴
if Find(A,target,0,N-1):
print(1)
else:
print(0)
결과 : 성공 !