Binary Search - 고정점 찾기

"""
고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다.
예를 들어 수열 a = [-15, -4, 2, 8, 13]이 있을 때,
a[2] = 2이므로, 고정점은 2가 된다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며,
모든 원소가 오름차순으로 정렬되어 있다.
이 때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성해라.
고정점은 최대 1개만 존재한다.
만약 고정점이 없다면 -1을 출력한다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다.
"""

"""
IDEA

mid 와 lst[mid]를 계산해 나간다.
mid는 인덱스로 0,1,2,3... 으로 진행한다. 해당 mid는 함수로 y = x 로 표현할 수 있다.
반면, lst는 오름차순으로 정렬된 수로 y = nx + m 의 함수로 진행이 된다. (고정점이 있는 경우이다.)
두 함수가 만나는 점이 고정점이 되는 것이다.

mid > lst[mid] ==> 두 함수가 만나는 고정점이 오른쪽에 있다는 의미로 오른쪽으로 이진탐색 진행
mid < lst[mid] ==> 두 함수가 만나는 고정점이 왼쪽에 있다는 의미로 왼쪽으로 이진탐색을 진행 
계속된 이진탐색의 반복을 제어하는 조건은 무엇인가?
==> lo, hi 보다 같아지면 고정점을 찾은것이기에, 즉, 끝까지 쪼개면서 진행을 한 것이기에 lo가 hi보다 작은 동안 진행을 한다.
"""

def fixed_point(lst):
    lo, hi = 0, len(lst)
    while lo < hi:
        mid = (lo + hi) // 2
        if mid > lst[mid]:
            lo = mid + 1
        else:
            # hi는 맨 처음 len(lst)로 실제 인덱스 보다 1 큰 수를 갖기에 -1을 해주지 않는다.
            hi = mid
    if lo >= len(lst) or lo != lst[lo]:
        return -1
    return lo




assert fixed_point([-1, 1, 3, 5, 7]) == 1
assert fixed_point([-15, -6, 1, 3, 7]) == 3
assert fixed_point([-15, -4, 2, 8, 9, 13, 15]) == 2
assert fixed_point([-15, -4, 3, 8, 9, 13, 15]) == -1
assert fixed_point([-15, -6, 1, 2, 5]) == -1
assert fixed_point([-15, -6, -5, -4, -3]) == -1
assert fixed_point([3, 4, 5, 6, 7]) == -1

해당 문제를 해결하기 위해서는 고정점이 생기는 경우를 함수의 그래프를 이용하여 이해하였다.