[python] 이분검색

[문제]

임의의 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())
a = list(map(int, input().split()))
s = 0
e = len(a) - 1

a.sort()

while s <= e:
    mid = (s+e)//2
    if a[mid] == m:
        print(mid+1)
        break
    elif a[mid] > m:
        e = mid - 1
    else:
        s = mid + 1

---

[내용]

1. 찾고자 하는 수를 두 부분으로 나눠서 찾는 기법 -> 주어진 탐색 리스트가 이미 정렬되어 있어야 함!!

2. s는 첫번째, e는 마지막, mid는 리스트의 중간값을 의미

3. mid 값과 찾고자 하는 값을 비교

- 찾고자 하는 값 == mid: 해당 인덱스 출력

- 찾고자 하는 값 > mid: e 값을 중간보다 왼쪽으로 이동

- 찾고자 하는 값 < mid: s 값을 중간보다 오른쪽으로 이동