파이썬 알고리즘-22 (탐색, 그리디) Binary Search

22.이분검색
임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수
중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는
프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

▣ 입력설명
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

▣ 출력설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
▣ 입력예제 1
8 32
23 87 65 12 57 32 99 81

▣ 출력예제 1
3

내 코드

n,m=map(int, input().split())
lst=list(map(int, input().split()))
lst.sort()

lt=0
rt=len(lst)-1
mid=(lt+rt)//2

while lst[mid]!=m:
    if lst[mid]>m:
        rt=mid-1
        mid=(lt+rt)//2
    elif lst[mid]<m:
        lt=mid+1
        mid=(lt+rt)//2
    

print(mid+1)

테스트케이스는 다 맞았는데 제대로 한건지 모르겠다.

풀이

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
        
print(cnt)

반성점

• 이진탐색은 수업에서 배웠는데 전혀 기억나지 않았다.

배운 것

• Binary Search: 배열이 정렬되어 있는 상태에서, 원하는 값이 중간값보다 큰지 작은지를 살펴본다. 중간값(mid) = (왼쪽인덱스lt+오른쪽인덱스rt)//2이고 중간값이 더 크면 왼쪽을 날리고 작으면 오른쪽을 날린 후 mid값을 조정해준다. 그리하여 lt>rt가 될 때까지 반복한다.