고정점 찾기

 

 

 

유형 파악 및 구현

이 문제는 두가지 방법으로 풀 수 있다. 파이썬에서 제공해주는 함수를 이용하거나 그냥 이진탐색을 내가 구현한다.

배열은 이미 정렬되어있다. "정렬되어 있는"이라는 말이 나오면 이진 탐색을 의심하는 것도 좋은 습관인 것 같다.

 

1. 이진 탐색 구현

방식은 그동안 하던 방식과 동일하다.

하지만 정당한지 봤을 때, 예를 들어 인덱스 2에 3이 있다고 가정하자. 인덱스 3부터는 value가 무조건 3보다는 클것이다.

따라서 이런 경우, 굳이 다음 부분을 확인할 필요가 없게 된다.

반대 경우도 마찬가지이다.

 

2. 함수 사용

bisect_left or bisect_right를 이용해 구현 가능하다. 이는 이진탐색을 기반으로 하는 탐색 알고리즘이다.

 

 

 

코드

arrays = [-15, -6, 1, 3, 7]
# arrays = [-15, -4, 2, 8, 9, 13, 15]
# arrays = [-15, -4, 3, 8, 9, 13, 15]


start = 0
end = len(arrays)

while start <= end:
    mid = (start + end) // 2
    if arrays[mid] == mid:
        print(mid)
        break
    elif arrays[mid] > mid:
        end = mid - 1
    else:
        start = mid + 1
if start > end:
    print("-1")








from bisect import bisect_left
result = False
for array in arrays:
    index = bisect_left(arrays, array)
    if index == array:
        result = True
        break
if result:
    print(index)
else:
    print("-1")