[이코테] 이진 탐색 - 고정점 찾기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

입력조건

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

출력조건

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

사고과정

• 문제에서 '모든 원소가 오름차순으로 정렬되어 있다'라는 포인트와 시간 복잡도 $O(logN)$으로 설계하지 않으면 안된다는 포인트 2개로 이진 탐색을 쉽게 떠올렸다. 그런데 특이한 점은 이진 탐색할 때, 탐색할 target 값이 중간(middle) 인덱스와 같은 경우를 출력하는 점이었다.
• 매번 이진 탐색 native python 소스 코드를 구현했던 점이 이진 탐색 로직을 쉽게 작성할 수 있게 했다. 단, 이진 탐색 시 어떨 때, 어느 방향을 선택해야 하는지, 즉, 예를 들어, 중간 인덱스와 탐색한 값 대소 비교 경우에 따라 왼쪽, 오른쪽 방향으로 움직이어야 하는지 알아내기 위해 입력 예시 데이터를 활용해 연습장에 그려보고 눈치를 챘다. 결국 array[mid_idx] < mid_idx 일 때는 오른쪽 즉, start_idx = mid_idx + 1 이고 array[mid_idx] < mid_idx 인 경우엔 왼쪽 즉, end_idx = mid_idx - 1 이어야 한다는 것을 알아냈다. 나중에 잘 생각해보니, 어차피 오름차순 정렬되어 있기 때문에 인덱스 값이 현재 탐색한 값보다 더 '크다'는 것은 타겟값과 인덱스가 똑같은 즉, 우리가 찾으려는 최종 값은 현재 탐색한 값보다 배열 순서 상으로 뒤에 있다는 걸 추측할 수 있기 때문에 오른쪽(start_idx = mid_idx + 1)으로 가야 한다는 것을 알 수 있다!
• 필자는 while문을 활용해서 구현했는데, 책 속에서는 재귀함수를 활용해 구현하였다.

풀이

1. 나의 풀이

import sys

N = int(input())
array = list(map(int, input().split()))
start = 0
end = N-1


def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == mid:
            return mid
        elif array[mid] < mid:
            start = mid + 1
        else:
            end = mid - 1
    return '-1'


res = binary_search(array, start, end)
print(res)

2. 책의 풀이

import sys

N = int(input())
array = list(map(int, input().split()))
start = 0
end = N-1


def binary_search(array, start, end):
    if start > end:
        return '-1'
    mid = (start + end) // 2
    if array[mid] == mid:
        return mid
    elif array[mid] < mid:
        return binary_search(array, mid+1, end)
    else:
        return binary_search(array, start, mid-1)


res = binary_search(array, start, end)
print(res)