[알고리즘 일기 - 파이썬] 182. 고정점 찾기

문제 182. (2022-02-12)

이코테 기출) 이분탐색. 고정점 찾기

[파이썬(python) - 이분탐색]

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

---

입력

• 첫째 줄에 N이 입력됩니다. (1 ≤ N ≤ 1,000,000)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
  (-10^9 ≤ 각 원소의 값 ≤ 10^9)

 

---

출력

• 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

 

---

입력 예시

5
-15 -6 1 3 7

 

---

출력 예시

3

 

---

❧ 정답

 

 

🔎IDEA) 이분탐색 - 이분탐색으로 리스트를 순회하며 고정점이 존재할 경우에만 출력을 한다.

• flag : 고정점이 존재하는 지 판단하는 변수

 

[Line 7 - 8]
👉 flag 값을 0으로 초기화 하여, 리스트를 모두 순회하는 동안 고정점이 존재하는 지를 판단한다.
👉 리스트의 길이만큼 start와 end 변수의 값을 초기화한다.

[Line 11 - 14]
👉 arr[mid] 값을 비교 값으로 하여 해당 값과 인덱스 값 mid를 비교하여 두 값이 같을 경우, 고정점이 존재하는 것이므로 해당 값을 출력하고 반복문을 빠져나온다.

[Line 16 - 19]
👉 만약 arr[mid] = -6, mid = 1 일 경우, arr[mid] 값보다 인덱스인 mid 값이 더 크다.
이때에는 인덱스 mid 이전에는 고정값이 존재하지 않는다. 따라서 start = mid + 1로 설정한 뒤 다시 탐색을 수행한다.
👉 arr[mid]가 mid 값보다 클 경우에도 인덱스 mid 이상으로는 고정값이 존재하지 않으므로 mid 값 미만의 값들로 다시 탐색을 진행한다.