문제)
답안 코드)
이분 탐색은 시간 복잡도 log_2 N을 보장한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import sys
#sys.stdin=open("input.txt", "r")
n, m=map(int, input().split())
a=list(map(int, input().split()))
a.sort()
lt=0#왼쪽 포인터
rt=n-1#오른쪽포인터
while lt<=rt: # 왼쪽 포인터가 커지면 종료
mid=(lt+rt)//2 #중간값
if a[mid]==m: #정답이라면
print(mid+1)
break
elif a[mid]>m:#중간값이 정답보다 크다면,
rt=mid-1
else:#작다면
lt=mid+1
|
cs |
'코딩테스트 with PYTHON' 카테고리의 다른 글
[python] 코딩테스트 대비 - 이분검색(최소 길이 구하기) (0) | 2022.01.14 |
---|---|
[python] 코딩테스트 대비 - 이분검색(랜선자르기) (0) | 2022.01.14 |
[python] 코딩테스트 대비 - 2차원 배열에서 회문 탐색 (0) | 2022.01.10 |
[python] 코딩테스트 대비 - 스토쿠 검사 (0) | 2022.01.10 |
[python] 코팅테스트 대비 - 2차원 배열 상하좌우 비교 (0) | 2022.01.10 |