이분 검색

이분 검색

임의의 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()))
arr = list(map(int, input().split()))
arr.sort()

lt, rt = 0, n-1
while True:
    mid = (lt+rt)//2
    if arr[mid]==m:
        print(mid+1)
        break
    elif arr[mid]>m:
        rt = mid-1
    else :
        lt = mid+1

 

mid = (lt+rt) // 2

a[mid] == m 인가를 확인한다.

 

a[mid]가 m보다 크다면, 더 작은 범위에 있는 것이므로, 큰 쪽을 버려준다.

즉, rt 값을 mid-1 로 바꾸어준다.

 

a[mid]가 m보다 작다면, 더 큰 범위에 있는 것이므로, 작은 쪽을 버려준다.

즉, lt 값을 mid+1 로 바꾸어준다.