[코딩테스트] 섹션 4-1. 이분 검색

강의명 : 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

 

문제

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

 

입력 설명

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

출력 설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

 

입력 예제

8 32 -> 8개의 수가 주어지며, 32 라는 숫자는 몇 번째에 위치 하는가?

23 87 65 12 57 32 99 81

 

출력 예제

3

 

정렬하면, 

12 23 32 57 65 81 87 99 가 된다.

 

맨 왼쪽 lt라는 변수가 필요함 (0번 인덱스를 가리킴)

맨 오른 rt라는 변수가 필요함 (끝 인덱스)

 

lt = 검사 범위 시작 지점

rt = 검사 범위 끝 지점

 

mid = (lt + rt) // 2 

 

위의 경우,

mid 가 3이 되는 것.

찾고자 하는 숫자 32(m)이라는 숫자가 

a[mid] == m 인지를 확인함. 맞다면 mid + 1 ( 인덱스 + 1 을 해야 번째를 가리킴)

 

a[mid] > m 이라면, 중간보다 이전에 있는 것. 이전~중간 범위 확인 rt = mid - 1

a[mid] < m 이라면, 중간보다 이후에 있는 것. 중간~이후 범위 확인 lt = mid + 1

 

 

이런 식으로 하면, 절반씩 툭툭 나가 떨어짐. 유효범위가 반씩 줄어드는 것.

처음에 정렬된 상태의 문자열이 필요함.

log N 번만에 이분 검색이 된다.

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 # 0번 인덱스 부터 들어갔으니 1 빼주기

while lt<=rt: # 범위가 좁아지다보면, 값이 같아지거나 작아지는 경우가 발생하면 탐색을 다 한 경우임
    mid=(lt+rt)//2
    if a[mid]==m: # 중간 값이 m이냐.
        print(mid+1) #번째 출력을 위해 1을 더해짐
        break
    elif a[mid]>m:
        rt = mid-1
    else:
        lt = mid+1