[알고리즘]이분검색

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

입력1

8 32
23 87 65 12 57 32 99 81

출력1

3

[내 코드]

def binary_search(x,start,end,find):
    
    while start<=end:
        mid=(start+end)//2
        if a[mid]==find:
            return mid+1
        elif x[mid]>find:
            end=mid-1
        else:
            start=mid+1
        

N,M=map(int,input().split())
a=list(map(int,input().split()))

a.sort()
mid=len(a)//2
num=binary_search(a,0,len(a)-1,M)
print(num)

1. 처음에는 재귀함수 구현을 통해서 했지만 in5.txt에서 runtime error가 발생하여 for문으로 구현
2. 이분검색알고리즘을 이용하여 찾는값이 mid값보다 크면 mid기준으로 우측에 있으므로 start값을 mid+1로 한다.
3. 찾는 값이 mid값보다 작으면 mid기준으로 좌측에 있으므로 end 값을 mid-1로 한다.

[해설코드]

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