Algorithm - 이분 검색

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[이분 검색]

 

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

N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면, 이분 검색으로 M이 정렬된 상태에서 몇 번째에 있는지를 구하는 프로그램을 작성하시오. (단, 중복값은 존재x)

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 1,000,000)과 M이 주어진다.

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

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_22.txt', 'rt')

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
        
# 출력 : 3

 

input_22.txt(입력)

8 32
23 87 65 12 57 32 99 81

 

 

중요내용

1. sort() 함수는 특정 리스트의 데이터를 오름차순으로 정렬시켜준다.
2. 변수 mid를 통해 원하는 데이터(m)을 찾는 방식으로, 만약 mid > m이면 포인트 변수 rt를 mid - 1 자리로 옮겨서 이분 검색을 다시 실행하고 반대로 mid < m이면 포인트 변수 lt를 mid + 1자리로 옮겨서 이분 검색을 다시 실행한다.
3. 즉, 포인트 변수 lt와 rt를 통해 범위를 줄임으로써 변수 mid가 원하는 데이터(m)에 도달 할 때까지 반복 실행된다.
4. 이분 검색은 밑이 2인 log n번 안으로 총 n개의 데이터 중 원하는 값을 찾는 검색 방법이다.