[알고리즘] 이분탐색

(문제) 이분탐색

---

임의의 N개의 숫자가 입력으로 주어집니다.

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

단 중복값은 존재하지 않습니다.

입력설명

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

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

출력설명

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

테스트케이스

입력예제	출력예제
8 32 23 87 65 12 57 32 99 81	3
15 99 73 32 31 49 94 37 40 62 78 66 27 100 99 29 9	14
30 57 6 32 38 1 28 76 51 8 98 88 74 60 65 57 97 63 56 99 85 5 13 100 61 36 44 50 62 41 91 9	16

---

해결방법

숫자 up & down을 생각해보면 간단하다.

우선 정렬을 해야한다.

정렬한 리스트에서 맨 앞 인덱스를 LT로

맨 마지막 인덱스를 RT로 포인터를 잡는다.

LT와 RT의 중앙 MID를 잡기 위해서 (LT + RT) // 2를 한다.

자! 아까 말한 숫자 UP & DOWN을 생각해보자.

A라는 사람에게 1 ~ 50 까지의 숫자 중에 하나의 숫자를 생각해 보라고 해보자.

우리가 이 사람이 생각한 숫자를 맞추려고 할 때, 중앙의 수 기준으로 자르지 않나?

25 인가? 물어보고 그 숫자가 아니면 A라는 사람은 A가 결정한 숫자가 내가 말한 숫자보다 UP인지 DOWN인지 알려준다.

이때 만약 A가 DOWN이라고 하면 우리는 25 이상인 숫자는 다 배제한다.

그러고 다시 1 ~ 25 사이의 숫자를 우리는 생각하여 물어 볼 것이고, 이것을 반복하여 숫자를 찾을 것이다.

이분탐색 방법은 이 방법과 동일하다.

만약 MID의 숫자가 결정한 숫자 보다 작으면 RT는 MID의 값이 되고

MID의 숫자가 결정한 숫자보다 클 경우 LT는 MID의 값이 되는 것이다.

LT가 만약 RT 이상이 될 경우 이 반복은 종료한다.

---

코드

n, m = map(int, input().split())

arr = list(map(int, input().split()))

# 이분 검색을 위한 정렬
arr.sort()

LT = 0
RT = len(arr) - 1

# 만약 끝까지 했는데, 동일한 구간이 생기는데, 이때 맞는 것이다.
# 시간 복잡도 0 (lon N)
while LT <= RT:
    MID = (LT + RT) // 2
    # MID + 1 혹은 MID - 1 하는 이유는 MID가 아니기 때문
    if arr[MID] == m:
        break
    if arr[MID] > m:
        RT = MID-1
    elif arr[MID] < m:
        LT = MID+1

print(MID+1)