인프런 커뮤니티 질문&답변
작성한 질문수
이분검색 질문있습니다.
작성
·
259
2
만약 리스트가 [1, 2, 2, 2, 3] 으로 주어진다면 즉 중복 값이 있는 리스트가 존재하면 이 방법으로 2의 위치는 3이 됩니다.
만약 중복일 경우 가장 빠른 값의 위치를 반환하라고 하면
어떤식으로 우회하여 실제 답을 찾을수 있을까요?
답변 2
0
0
김태원
지식공유자
문제 설명이 디테일 하지 못했습니다. 중복값은 존재하지 않는다라고 문제에 설명해 놓겠습니다.
물어보신 것 처럼 중복값이 있을 때 가장 빠른 값의 위치를 반환하려면 이분 검색을 하면서 답을 찾았을 때 멈추지 말고 답을 계속 갱신하면서 범위를 앞쪽으로 좁혀가면 됩니다.
아래는 질문하신 답을 찾는 코드입니다.
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:
res=mid+1
rt=mid-1
elif a[mid]>m:
rt=mid-1
else:
lt=mid+1
print(res)