이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

✅ 문제

고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 워노가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -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

💻 코드

N = int(input())

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

start = 0
end = len(data) -1
result =0

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
    result = -1

print(result)

설계

이진 탐색으로 중간값과 그 인덱스를 확인한다. 일치하면 중간값이 고정값이다.
중간값이 인덱스보다 크다면 그 인덱스 오른쪽 값들은 자기 인덱스보다 무조건 값이 크다. 따라서 end를 mid - 1로 바꿔 이진 탐색을 계속 진행한다.
중간값이 인덱스보다 작다면 그 인덱스 왼쪽 값들은 자기 인덱스보다 무조건 값이 작다. 따라서 start를 mid + 1로 바꿔 이진 탐색을 계속 진행한다.

📝 정리

문제를 풀기 전에 어떻게 풀어야 할 지 간단히 메모하면서 풀었더니 금세 풀었다. 앞으로 메모하면서 정리한 후 코딩을 해야겠다.