[이분탐색(결정알고리즘)][그리디 알고리즘] - 이분 검색

문제

• N개의 수를 오름차순하여 M값이 몇번째에 존재하는지 출력하라
• 단 중복값은 존재하지 않는다.

문제 풀이 - 1 

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

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

a.sort()

num = a.index(m)

print(num+1)

• 정렬한 값을 index()를 사용해서 해당 인덱스를 가져오고 0부터 시작하지만 우리는 1부터 시작한다는 가정하에 문제를 진행하기에 +1 해준다.

문제 풀이 - 2

#이분탐색으로 문제 풀이
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

• point를 왼쪽끝 오른쪽 끝에서 시작해서 해당 mid 값이 찾고자하는 값보다 큰지 작은지를 판별해 범위를 줄여가며 m을 찾는 문제이다.

• a[mid]는 현재 57 값으로 이 mid에 있는 값이 m보다 크기 때문에 rt 값을 mid 바로 앞으로 변경해준다.
• mid값이 m값보다 작은 경우엔 lt 값을 mid 바로 뒤로 변경해서 범위를 줄여 찾아간다.