8.3 마술인덱스

문제

배열 A[0 ... n-1]에서 A[i] = i  인 인덱스를 마술 인덱스(magic index)라고 한다. 정렬된 상태의 배열이 주어졌을때 마술 인덱스가 존재한다면 그 값을 찾는 메서드를 만들어라.

 

해결법

가장 무식하고 간단하게 푸는 방법은 0부터 순환하면서 해당하는 index가 있는지 확인하는 것이다.

하지만 정렬된 데이터라는 점에서 이진 탐색 으로 문제를 해결 할 수 있을 것 같다. 

중복된 데이터가 없다는 가정하에는 

-40	-20	-1	1	2	3	5	7	9	12
0	1	2	3	4	5	6	7	8	9

이러한 데이터가 있다고 보자 

A[5] = 3 A[mid] < mid 이므로 마술인덱스는 오른쪽에 있음을 알 수 있다. 

정말 왼쪽에 있을 수는 없을까? i에서 i-1로 움직인다고 가정해보자. 이 때 배열의 원소값도 적어도 1만큼 감소한다. 

따라서 원소의 값이 이미 index보다 작다면 index가 k만큼 작아질때 원소 값도 적어도 k만큼 적어지므로 절대 같아 질 수 없다. 

재귀로 코드를 작성해보자

def Solution(array):
    return findMagicIndex(array, 0, len(array)-1)

def findMagicIndex(array, l, r):
    if l > r :
        return -1
    mid = (l + r) / 2
    if mid == array[mid]:
        return mid
    elif mid < array[mid]:
        return findMagicIndex(array, l, mid-1)
    else :
        return findMagicIndex(array, mid+1, l)

반복적으로 연산하는 방법으로 해결해보자 

def Solution(array):
    
    l , r = 0 , len(array)-1
    while l <= r :
        mid = (l + r) / 2
        if mid == array[mid]:
            return mid
        elif mid < array[mid]:
            r = mid -1
        else :
            l = mid +1
    return -1