マジックインデックス
問題
ソートされた配列から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)