[Algorithm] 이분탐색

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

이분탐색을 몰라서 우선 인덱스 하나하나에 접근하여 비교하는 방식으로 구현하였다.

<내 답안>

n, m = map(int, input().split())
li = list(map(int, input().split()))
li.sort()
for i in range(n):
    if li[i] == m:
        print(i+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

이분탐색을 이용하면 log(n)번만 실행하기 때문에 훨씬 효율적인 코드이다.

이분탐색은 정렬된 자료를 반으로 나누어 탐색하는 것이다.

내 코드는 순차탐색을 사용한 것인데, 이분탐색이 시간이 더 적게 걸려 효율적이다.
여기서 중요한 점은, 이분탐색을 사용하기 위해서는 오름차순으로 정렬된 자료여야 한다는 것이다.

• 맨 왼쪽 인덱스를 가르키는 lt, 맨 오른쪽 인덱스를 가르키는 rt 변수 만들기
• 정 중앙 인덱스를 가르키는 mid 변수 만들기
• mid = (lt + rt) // 2

만약 m이 mid보다 작다면 rt는 mid-1이 될 것이고, mid보다 크다면 lt가 mid+1이 될 것이다.