Python 고정점 찾기

문제에서 O(logN)으로 알고리즘을 설계하기를 요구했다 -> 선형탐색은 O(N) 이므로 부적합

데이터 셋이 오름차순으로 정렬되어 나오기 때문에 이진탐색을 선택함

mid 를 인덱스로 보고 array[mid] 값과 같으면 고정점이다 -> 이 값을 리턴

그렇지 않은 경우, array[mid] 실제 값이 더 크다면 반으로 뚝 자른 데이터들 중에서 오른쪽의 큰 값들을 탐색하면 된다.

더 작으면 왼쪽의 작은 값들을 탐색한다.

탐색 실패하면 None을 반환한다.

 

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

def binary(array, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    if array[mid] == mid:
        return mid
    elif array[mid] < mid:
        binary(array, mid+1, end)
    else:
        binary(array, start, mid-1)
        
count = binary(array, 0, n-1)

if count == 0:
    print(-1)
else:
    print(count)