[파이썬 알고리즘] 이분 검색

이분 검색

📄 문제

임의의 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

🧞 풀이

풀이

# 입력: 첫 줄에 자연수 n, m, 두 번째 줄에 n개의 수가 공백을 사이에 두고 주어짐
# 출력: 첫 줄에 정렬 후 m의 값의 위치 번호를 출력

n, m = map(int, input().split())                                    # n, m 입력 및 할당
n_list = list(map(int, input().split()))                            # 숫자 리스트 입력 및 할당

n_list = sorted(n_list)                                             # n_list 오름차순 정렬

c = 0                                                               # 순서 담을 c 할당

for i in n_list:                                                    # n_list 요소 반복
    c += 1                                                          # c 1씩 증가
    if i == m:                                                      # 만약 i가 m이면
        print(c)                                                    # c 출력
        break                                                       # 반복문 종료

 

다른 사람 풀이

# 이분검색

'''
lt, rt
0 1 2 3 4 5 6 7
12 23 32 57 65 81 87 99

mid = (lt + rt) // 2

3 = mid

a[mid] == m

rt = mid - 1
lt = mid + 1

절반씩 좁혀 나감

1 = mid

lt, rt = 2

만약 1024개의 데이터가 있다면
512개로 줄어듦
256으로 절반으로 줄어듦
128씩 작아지면

이분검색 log n번만에 된다.
'''

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