[김태원 알고리즘] 이분검색

사용 언어: Python3

문제

풀이

내 풀이

N, M = map(int, input().split())
lst = list(map(int, input().split()))

lst.sort()
src, dest = 0, N-1
ans = -1
while True:
    mid = lst[(dest-src+1)//2]
    if M == mid:
        ans = lst.index(mid)
        break
    if M < mid:
        dest = lst.index(mid)
    else:
        src = lst.index(mid)

print(ans+1)

• dest = lst.index(mid), src = lst.index(mid)이 맞는지 잘 모르겠다.. -> 아니었음!

다른 풀이

N, M = map(int, input().split())
lst = list(map(int, input().split()))

lst.sort()
src, dest = 0, N-1
while src <= dest: # ✅ src가 dest보다 작거나 같은 동안만
    mid = (src+dest)//2 # mid는 인덱스
    if lst[mid] == M:
        print(mid+1)
        break
    elif lst[mid] > M:
        dest = mid-1
    else:
        src = mid+1

• while문 범위 확인
• dest = mid-1, src = mid+1으로 업데이트!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기