이코테 - Ch15. 고정점 찾기 (이진탐색)

#1. 설계 및 풀이

 

# 고정점 찾기

'''
입) n (1이상 백만이하)
n개의 원소 (원소의 값은 -10억이상 10억 이하)

출) 고정점 출력, 없으면 -1 출력

-고정점이란 그 값이 인덱스와 동일한 원소, 최대 1개만 존재

-서로 다른 원소를 포함한 수열이 오름차순으로 정렬되어있음

-O(logN)으로 설계

# 설계

이진탐색

값이 인덱스보다 작으면 인덱스가 큰 값에 대해 이진탐색 수행
값이 인덱스보다 크면 인덱스가 작은 값에 대해 이진탐색 수행

'''
import sys
input = sys.stdin.readline

n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))

ans = -1
start, end = 0, n-1

while start <= end :
    mid = (start + end) // 2

    if arr[mid] == mid :
        ans = mid
        break

    elif arr[mid] < mid :
        start = mid+1

    else :
        end = mid - 1

print(ans)

 

 

#2. 개선할 점

 

- 재귀로도 풀 수 있다.

 

# 고정점 찾기

import sys
input = sys.stdin.readline

def binary_search(arr, start, end) :

    if start > end :
        return -1

    mid = (start + end) // 2

    if arr[mid] == mid :
        return mid

    elif arr[mid] < mid :
        return binary_search(arr, mid+1, end)

    else :
        return binary_search(arr, start, mid-1)

    

n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))


print(binary_search(arr, 0, n-1))