고정점 찾기 (이진 탐색)

03 Feb 2021 in ALGORITHM

‘풀이시간 20분 , 시간제한 1초, 메모리제한 128MB, 출처 Amazon 인터뷰 (취코테 368p)’

아주 기본적인 이진탐색 문제이다. 배열을 array라고 할 경우 배열의 인덱스의 값과 인덱스가 같은 값을 찾기만 하면 된다. 이 경우가 고정점이기 때문이다.

만약 배열의 mid 인덱스 값이 mid보다 크다면 array는 정렬되어 있으므로 배열의 오른쪽도 당연히 크기 때문에 이쪽 범위는 탐색할 필요가 없으므로 범위를 start ~ mid-1로 설정하면 되고, 작다면 왼쪽또한 작기 때문에 작은 범위를 제외한 mid+1 ~ end로 범위를 설정하면 된다.

def binary_search(array, start, end):
  if start > end:
    return None
  mid = (start + end) // 2
  # 고정점을 찾은 경우 인덱스 반환
  if array[mid] == mid:
    return mid
  # 중간점이 가리키는 위치의 값보다 중간점이 작은경우 왼쪽 확인
  elif array[mid] > mid:
    return binary_search(array, start, mid - 1)
  # 중간점이 가리키는 위치의 값보다 중간점이 큰 경우 오른쪽 확인
  else:
    return binary_search(array, mid + 1, end)

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

# 이진 탐색(Binary Search) 수행
index = binary_search(array, 0, n - 1)

# 고정점이 없는 경우 -1 출력
if index == None:
  print(-1)
# 고정점이 있는 경우 해당 인덱스 출력
else:
  print(index)