[python] 이진 탐색 알고리즘

배열이 주어진다. 배열의 원소는 오름차순으로 주어진다. 만약 배열에서 "값이 인덱스와 동일한 원소"인 고정점을 찾는다면 그 값을, 고정점이 없으면 "-1" 을 출력해보자.

 

주의) 이것을 O(logN) 의 시간 복잡도로 해결해야만 한다.

 

O(logN) 이라는 것은 전체 배열의 순차적 탐색이 아니라 이진 탐색을 해야함을 의미 한다.

 

from sys import stdin

N = int(input())
li = list(map(int,stdin.readline().split()))

start = 0
end = N-1

while start < end:
    mid = (start + end) // 2
    if li[mid] == mid:
        print(mid)
        exit()
    elif li[mid] > mid: # 더 작음
        end = mid
    elif li[mid] < mid:
        start = mid + 1

print(-1)

 

1. 원소 시작 index 를 start, 원소의 끝 index 를 end 로 하자. (만약 배열길이가 4면, start=0, end=3)

2. 확인할 값 mid 를 start와 end의 중간으로 정한다.

3. 만약 li[mid] 값이 해당 인덱스보다 작다면, 오름차순 정렬된 배열이므로 오른쪽 부분을 간다.

3. 만약 ... 크다면 왼쪽 부분을 간다.

4. 오른쪽 부분이면 start 를 mid + 1 로 한다.

5. 왼쪽 부분이면 end = mid 로 한다.

6. 만약 start가 end와 같거나 커지면 종료한다.