백준 이분탐색 문제입니다.
문제
https://www.acmicpc.net/problem/1920
[나의 풀이]
M = int(input())
check = list(map(int,input().split()))
for x in check:
v = bisect(array,x)
if array[v-1] == x:
print(1)
else:
print(0)
이분 탐색을 모듈로 구현한 bisect 함수를 사용하였습니다. bisect 함수는 배열안의 찾고자하는 요소의 인덱스를 반환하는 함수입니다. 이때, 찾고자 하는 요소가 배열에 없을 때는 0 or 길이-1 라는 인덱스를 반환하기 때문에 array[반환된 인덱스]를 확인하는 조건문을 통해 해결하였습니다.🦝🦝🦝
[다른 사람의 풀이]
# 입력
N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))
A.sort() # A 정렬
# arr의 각 원소별로 이분탐색
for num in arr:
lt, rt = 0, N - 1 # lt는 맨 앞, rt는 맨 뒤
isExist = False # 찾음 여부
# 이분탐색 시작
while lt <= rt: # lt가 rt보다 커지면 반복문 탈출
mid = (lt + rt) // 2 # mid는 lt와 rt의 중간값
if num == A[mid]: # num(목표값)이 A[mid]값과 같다면 (목표값 존재여부를 알았다면)
isExist = True # isExist Ture 변경
print(1) # 1 출력
break # 반복문 탈출
elif num > A[mid]: # A[mid]가 num보다 작으면
lt = mid + 1 # lt를 높임
else: # A[mid]가 num보다 크다면
rt = mid - 1 # rt를 낮춤
if not isExist: # 찾지 못한 경우
print(0) # 0 출력
다른 사람의 풀이로는 직접 이분 탐색을 구현한 뒤 저의 풀이처럼 반환된 인덱스를 array에서 재확인하여 판별하는 방식이었습니다.
감사합니다.🐲🐲🐲