[이진탐색] 고정점 찾기

문제

이코테 368p

접근

모든 수열이 오름차순 정렬 + 특정 조건 맞는 것 search -> 이진탐색이구나

코드

arr_len = int(input())
arr = list(map(int, input().split()))

answer, start, end = -1, 0, len(arr)-1

while (start <= end) : 
  mid = (start+end)//2
  if arr[mid] == mid : # 정답
    answer = mid
    break
  elif arr[mid] < mid : # arr[인덱스]<인덱스 라면 더 오른쪽을 찾아봐야한다
    start = mid + 1
  else : # 인덱스 < arr[인덱스]라면 더 왼쪽을 찾아봐야한다
    end = mid - 1

print(answer)

느낀점

이진탐색은 풀면풀수록 {조건}에 맞는지 안맞는지를 기준으로 left, right를 조정해나가면서 search 해나가는 것 같다. {조건}을 잘 생각해서 정하면 다 잘 풀 수 있을 것 같다!