[Amazon 인터뷰] 고정점 찾기

출처 : <이것이 코딩테스트다> -한빛미디어

 

초기접근

---

• 이진 탐색으로 data[mid] == mid 인지 확인해서 왼쪽, 오른쪽으로 나누려고 시도.
• 그런데 왼쪽, 오른쪽 나누는 기준을 모르겠음. 어떨때 왼쪽? 어떨때 오른쪽?
• data[mid-1] < mid -1 이면 왼쪽,
  data[mid+1] > mid + 1 이면 오른쪽 으로 나눴음
• 그랬더니 mid가 0일때 무한루프에 빠짐.

 

반복문으로 이진탐색을 구현할때 내가 실수했던 점

1. while start <= end: 로 하지 않고 while True: 로 했었음. (무한루프의 원인 중 하나)
2. 매우 간단했던 조건을 생각해내지 못함. 어렵게 생각했음.

 

 

 

해결 아이디어

---

data[mid] < mid 이면 왼쪽, data[mid] > mid 이면 오른쪽으로 풀면 끝

 

 

정답 코드

---

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

start = 0
end = n-1

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

    if data[mid] == mid:
        result = mid
        break
    elif data[mid] > mid:
        end = mid-1
    else:
        start = mid+1

print(result)