임의의 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이 될 것이다.
