[이진 탐색] 고정점 찾기

1. 문제

array가 정렬되어 주어질 때, index와 array[index]의 값이 같으면 출력,

하나도 없다면 -1을 출력

 

2. 입력

# SET - 1
N = 5
arr = [-15, -6, 1, 3, 7]

SET - 2
N = 7
arr = [-15, -4, 2, 8, 9, 13, 15]

SET - 3
N = 7
arr = [-15, -4, 3, 8, 9, 13, 15]

 

3. 출력

# SET - 1
3

# SET - 2
2

# SET - 3
-1

 

4. 풀이

이진탐색 패키지를 쓰지않고, 이진탐색을 구현해야 하는 문제

 

for문으로 N만큼 하나씩 돌면서 값이랑 index랑 같은지 찾는방법도 있지만, 그것은 시간 복잡도가 O(N)이므로 패스

O(logN)으로 풀려면 이진탐색을 사용해야한다.

 

array를 반으로 줄여나가며 (시작점과 끝점 설정)

가운데 index인 mid가 배열의 값과 같으면 return한다.

5. 코드

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

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)

index = binary_search(arr, 0, N-1)

if index == None:
    print(-1)
else:
    print(index)