문제 / 이분 검색 / 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

---

나의 풀이 (함수로 하면 왜인지 while문을 탈출하질 못한다...)

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

def solution(n,m,numbers):
    answer = 0
    numbers.sort()
    rt = n
    lt = 0

    while lt <= rt:
        mid = (rt + lt) // 2
        if numbers[mid] == m :
            answer = mid
            break
        elif numbers[mid] > m:
            rt == mid - 1
        elif numbers[mid] > m:
            lt == mid + 1

    return answer

print(solution(n,m,numbers))

 

모범답안

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

---

※ 알아야 할 것

- 이분 탐색 알고리즘은 rt = (리스트의 길이) lt = 0 (리스트의 처음 값)를 두고, mid = (rt + lt) // 2 중간 값을 설정하여 점차 mid 값을 줄여나감

 

- 이분 검색은 결정알고리즘에서 주로 이용한다.