[코테 스터디] 이진 탐색, 고정점

Q28. 고정점

🐣문제

고정점이란 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 a[2]=2이면 고정점은 2가 됩니다.


하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다.

🐥풀이

이진 탐색 알고리즘으로 접근해보자-!
오름차순 정렬에서 중간점(mid)의 값과 인덱스를 비교했을 때,
인덱스>값이면 오른쪽을 탐색한다. (값이 인덱스보다 더 커야하므로!)
인덱스<값이면 왼쪽을 탐색한다. (값이 인덱스보다 더 작아져야하므로!)
인덱스==값이면 고정점을 찾았으므로 고정점을 출력한다.

🐓코드

n = int(input())
num = list(map(int, input().split()))

start, end, result = 0, len(num), -1

# 이진탐색
while start<=end:
  # 중간 탐색
  mid = (start+end)//2

  # 인덱스와 해당 인덱스의 값이 같으면 고정점
  if num[mid]==mid:
    result = mid
    break

  # 인덱스보다 값이 더 크면 왼쪽 탐색
  if num[mid]>mid:
    end = mid-1
  # 인덱스보다 값이 더 작으면 오른쪽 탐색
  else:  
    start = mid+1

print(result)

⭐2022.05.03

이진탐색을 가볍게 연습해보기 좋은 문제-!