고정점 찾기

고정점 찾기

해결방법

문제에서 고정점이란: 수열의 원소 중에서 그 값이 인덱스와 동일한 원소

문제에서 O(logN)으로 해결해야 한다는 걸 보고 바로 이진탐색을 떠올릴 수 있어야 한다.

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

def search_fix(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == mid:
            return mid
        elif array[mid] < mid:
            start = mid + 1
        else:
            end = mid - 1
    return False

result = search_fix(array, 0, len(array) - 1)
if result == False:
    print(-1)
else:
    print(result)