マジックインデックス

問題

ソートされた配列からA[i] = iとなるindexを探す。配列が重複した値を持つ場合にどうするか。

考え方

2分探索的な方法で探す。

重複した値がある時は少しややこしくて、結局両側を探すしかない。ただし、探す範囲は mid > A[mid]ならば、左側はindexが0 ~ A[mid]の間 だけ探せば良い。 また、mid < A[mid]ならば、右側はindexがA[mid] ~ A.lengthの間だけ探せば良い。

コード例

import random

def magicIndex(A, start, end):
    mid = (start+end)//2
    if A[mid] == mid:
        return mid
    elif A[mid] < mid:
        return magicIndex(A, mid+1, end)
    elif A[mid] > mid:
        return magicIndex(A, start, mid-1)
    return False

def magicIndex2(A, start, end):
    # 重複のあるデータ
    if end < start:
        return -1
    mid = (start+end)//2
    if A[mid] == mid:
        return mid
    # left check
    left = min(mid-1, A[mid])
    leftvalue = magicIndex2(A, start, left)
    if(leftvalue >= 0):
        return leftvalue
    # right check
    right = max(mid+1, A[mid])
    rightvalue = magicIndex2(A, right, end)
    if(rightvalue >= 0):
        return rightvalue
    return False


if __name__ == "__main__":
    A = [random.randint(0, 10) for _ in range(20)]
    A = sorted(A)
    print(A)
    temp = magicIndex2(A, 0, len(A)-1)
    print(temp)
    #--magicindexない場合
    A = [random.randint(20, 50) for _ in range(20)]
    A = sorted(A)
    print(A)
    temp = magicIndex2(A, 0, len(A)-1)
    print(temp)

参考

問題は 世界で闘うプログラミング力を鍛える本 | マイナビブックス から