이코테 - 고정점 찾기

🐶 문제

주어진 수열 중에서 그 값이 인덱스와 동일한 원소 찾기

ex) 수열 a = {-15, -4, 2, 8, 13}이면 a[2] = 2 이므로 고정점은 2가 됨.

수열은 오름차순으로 정렬되어 있음

고정점이 없다면 -1을 출력함

시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과가 남

 

🐶 생각

이 문제 또한 O(logN)의 시간 복잡도를 넘게 되면 시간 초과가 나기 때문에, O(N)의 시간 복잡도를 가진 선형 탐색으로는 풀 수 없다.

따라서 이진 탐색을 구현해야 함!

단순히 이진 탐색 알고리즘을 알기만 하면 쉽게 풀 수 있는 문제이다.

 

🐶 문제 풀이

import sys
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

def binary_search(start, end):
  global nums
  while start <= end:
    mid = (start + end) // 2
    if nums[mid] == mid:
      return mid
    elif nums[mid] <= mid:
      start = mid + 1
    else:
      end = mid - 1
  return -1

result = binary_search(0, len(nums)-1)
print(result)