4.1 이분 검색

이분 검색: 범위를 반으로 나누면서 해당값을 찾는다

log2(N) 횟수만 찾으면 해당값의 위치를 알 수 있다

 

문제: 임의의 n개의 숫자가 입력으로 주어진다. n개의 수를 오름차순으로 정렬한 다음 n개의 수 중

한 개의 수인 m이 주어지면 이분 검색으로 m이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 

작성하시오. 

n, m =map(int, input().split())
#n: 주어지는 숫자의 개수 m:찾고자 하는 수
num_list=list(map(int, input().split()))
num_list.sort()
#정렬 함수 sort()

lt=0    #left-->lt
rt=n-1  #right-->rt

while lt<=rt:
    mid=(lt+rt)//2  #중간값 지정
    if num_list[mid]==m:
        print(mid+1)
        break
        #중간값 위치의 수가 찾고자 하는 수와 일치할 경우 루프 종료
        
    elif num_list[mid]>m:
        rt=mid-1
        #중간 위치의 숫자가 찾고자 하는 수보다 큰 경우
        #찾는 값이 중간 위치보다 왼쪽에 위치하므로 rt를 mid-1의 값으로 지정

    else:
        lt=mid+1
        #중간 위치의 숫자가 찾고자 하는 수보다 작은 경우
        #찾는 값이 중간 위치보다 오른쪽에 위치하므로 lt를 mid+1의 값으로 지정