[이진탐색] 고정점 찾기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분

1. 문제 설명

- 인덱스와 값이 일치하는 것을 '고정점'이라고 한다. 고정점이 있다면 이를 리턴하고, 아니라면 -1을 리턴하는 문제

2. 접근 방식

- 이진 탐색을 활용하고, 고정점을 target으로 생각하면 된다.

3. 코드

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

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

print(binary(array, 0, n-1) if binary(array, 0, n-1) else -1)

4. 코멘트

- 초기에 이진 탐색으로 방향을 쉽게 정하긴 했는데, 재귀로 구현할 지 반복으로 구현할 지 쓸데없는 고민이 좀 있었던 것 같다. 그리고 재귀로 풀 때에 뭘 리턴해야 하나 약간 가물가물하고 그랬던 것 같다. 보통 return할 게 없으면 none을 리턴하면 된다.

- 이진탐색 사용하는 법이 완전히 체화되지 않았었던 것 같다.