고정점 찾기

💻 입력 조건

• 첫째 줄에 N이 입력됩니다. ($1 <= N <= 1,000,000$)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
  ($-10^9$ <= 각 원소의 값 <= $10^9$)

💻 출력 조건

• 고정점을 출력합니다. 고정점이 없다면 -1을 출력합니다.

💻 입력 예시 1

5
-15 -6 1 3 7

💻 출력 예시 1

3

💻 입력 예시 2

7
-15 -4 2 8 9 13 15

💻 출력 예시 2

2

💻 입력 예시 3

7
-15 -4 3 8 9 13 15

💻 출력 예시 3

-1

📖 문제 해결
모든 원소가 오름차순으로 정렬되어 있으며, 시간 복잡도 O(logN) 으로 알고리즘을 설계하지 않으면 '시간 초과'판정을 받는다고 명시되어 있기에 이진 탐색을 이용하여 문제를 해결하고자 하였습니다.
이진 탐색의 기본 알고리즘을 활용하되, 반복문 내에 있는 if - elif - else 조건문은 문제에 맞추어 수정하였습니다. 인덱스의 값(mid)과 원소의 값(array[mid])이 같다면 해당 인덱스를 반환하고, 인덱스의 값보다 원소의 값이 작다면 오른쪽을 탐색하도록 하였습니다. 그리고 마지막으로 둘의 경우가 모두 아닌 경우(인덱스의 값보다 원소의 값이 크다면) 왼쪽을 탐색하도록 함으로써 고정점을 찾을 수 있도록 하였습니다. 또 고정점이 존재하지 않는다면 문제에서 제시한 바와 같이 -1을 반환할 수 있도록 코드를 추가하였습니다.

# n 입력받기
n = int(input())

# input_list 입력받기
input_list = list(map(int,input().split()))

# 이진 탐색을 이용하여 고정점을 찾는 함수
def binary_search(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
    
    # 고정점이 없다면 -1을 출력
    return -1

binary_search(input_list, 0, n-1)