# Chap 15. 이진탐색 - Q28. 고정점 찾기

- Author: @mildsalmon
- Published: 2021-10-12
- Updated: 2021-10-27
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-chap-15-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-%EA%B3%A0%EC%A0%95%EC%A0%90-%EC%B0%BE%EA%B8%B0
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 이진탐색, 고정점찾기

---

# 1. 고정점 찾기

- 난이도
	- 중하
- 풀이 시간
	- 20분
- 시간 제한
	- 1초
- 메모리 제한
	- 128 MB
- 출처
	- Amazon 인터뷰

### A. 📜 문제

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다.

하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하고, 고정점이 없다면, - 1을 출력한다.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다.

##### a. 예를 들면. 

고정점을 예를 들면 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2이므로, 고정점은 2가 된다.

##### b. 입력 조건

- 첫째 줄에 N이 입력된다.
	- 1 <= N <= 1,000,000
- 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다.
	- -10e9 <= 각 원소의 값 <= 10e9

##### c. 출력 조건

- 고정점을 출력한다, 고정점이 없다면 -1을 출력한다.

##### d. 테스트 케이스

- 입력 예시

	```

	5
	-15 -6 -1 3 7

	```

	```

	7
	-15 -4 2 8 9 13 15

	```
	
	```

	7
	-15 -4 3 8 9 13 15

	```
- 출력 예시

	```

	3

	```
	
	```

	2

	```
	
	```

	-1

	```
	
### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

def bi(start, end):
    if start <= end:
        mid = (end + start) // 2

        if mid == array[mid]:
            answer = mid
        elif mid > array[mid]:
            answer = bi(mid+1, end)
        elif mid < array[mid]:
            answer = bi(start, mid-1)
        return answer
    else:
        return -1

global array

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

start = 0
end = len(array)

array.sort()

answer = bi(start, end)

print(answer)

```

##### b. 😊 2차 시도 (성공)

```python

n = int(input())  
array = list(map(int, input().split()))  
  
start = 0  
end = n  
answer = None  
  
while start <= end:  
    mid = (start + end) // 2  
  
 if mid == array[mid]:  
        answer = mid  
        break  
  
 if mid < array[mid]:  
        end = mid - 1  
 elif mid > array[mid]:  
        start = mid + 1  
  
if answer == None:  
    print(-1)  
else:  
    print(answer)

```

##### c. 🙄 회고

> 내 풀이

- O(logN)이라서 이진탐색을 구현했다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2021/10/12/2021_10_12_9_F44tRKeGZD62wwcazX2Z.jpg)

##### a. 책 답안

[python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/15/2.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년