[이것이 코딩 테스트다 with Python] 고정점 찾기 : 이진탐색

문제

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

하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다.

이때 이 수열에서 단 하나의 고정점이 있다고 가정하고, 고정점을 출력하는 프로그램을 작성하시오.

없다면 -1을 출력하시오. 시간 복잡도는 O(logN)으로 설계해야 한다.

 

 

입력 조건

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

 

출력 조건

• 고정점을 출력하고 없다면 -1을 출력한다.

 

입력 예시 1

5 -15 -6 1 3 7

 

출력 예시 1

3

 

 

입력 예시 2

7 -15 -4 2 8 9 13 15

 

출력 예시 2

2

 

 

입력 예시 3

7 -15 -4 3 8 9 13 15

 

출력 예시 3

-1

 

---

✔ Solution

def binary_search(arr, start, end):
    # 존재하지 않으면 -1 반환
    if start > end:
        return -1
    mid = (start + end) // 2  # 중간값 = 고정값
    # 찾으면 인덱스 반환
    if arr[mid] == mid:
        return mid
    # 찾지 못했을 경우 start,end 수정하여 다시 탐색
    elif arr[mid] > mid:
        return binary_search(arr, start, mid - 1)
    else:
        return binary_search(arr, mid + 1, end)


n = int(input())
arr = list(map(int, input().split()))
result = binary_search(arr, 0, n - 1)
print(result)

 

⭐ 문제 포인트

• 배열이 이미 정렬 되어 있으므로 이진탐색으로 값을 찾는다.
• 고정점의 값을 중간점이라 놓고 탐색한다.