고정점 찾기 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 28, p 368

 

반복문으로 구현한 이진 탐색 코드를 참고하여 풀이했습니다.
고정점을 찾기 위해 if, elif, else 조건만 바꿔주어, 고정값을 찾으면 고정값을 반환하고, 현재 인덱스보다 현재 값이 더 큰 경우 왼쪽으로 이동(end를 mid-1로 갱신), 현재 인덱스보다 현재 값이 더 작은 경우 오른쪽으로 이동(start를 mid+1로 갱신)시킵니다.

 

https://codlingual.tistory.com/189

이진 탐색

 

def fixed_point_search(array, start, end):
    while start <= end:
        mid = (start+end)//2
        # 고정점이 있으면 고정점 출력 
        if array[mid] == mid:
            return mid
        # 현재 인덱스보다 값이 큰 경우, 왼쪽으로 이동
        elif array[mid] > mid:
            end = mid - 1
        # 현재 인덱스보다 값이 작은 경우, 오른쪽으로 이동
        else:
            start = mid + 1
    
    # 고정점이 없다면 -1 출력 
    return -1
    
def solution(n, array):
    N = len(array)
    return fixed_point_search(array, start=0, end=N-1)