Pythonで固定点（Fixed Point）を求める：A[i] == i となる最小のインデックスを見つける方法

問題概要

昇順にソートされた、重複のない整数の配列 A が与えられたとき、A[i] == i を満たす最小のインデックス i を返します。該当する i が存在しない場合は -1 を返します。

例えば、配列が [-10, -5, 0, 3, 7] の場合、A[3] = 3 が成立するため、出力は 3 となります。

解法のアプローチ

最もシンプルな解法は、配列を先頭から順に確認していく線形探索です。手順は以下の通りです。

• インデックス i を 0 から配列の長さ - 1 まで順に調べる
• i == A[i] が成立した時点で、その i を返す（先頭から探索しているため、必ず最小のインデックスになる）
• ループが終了しても見つからなければ、-1 を返す

Pythonでの実装例

以下のコードで具体的な実装を確認できます。

class Solution(object):
    def fixedPoint(self, A):
        for i in range(len(A)):
            if i == A[i]:
                return i
        return -1

ob1 = Solution()
print(ob1.fixedPoint([-10,-5,0,3,7]))

入力

[-10,-5,0,3,7]

出力

3

計算量と改善案：二分探索による高速化

上記の線形探索の時間計算量は O(n) です。しかし、この問題では配列が昇順にソートされ、かつ要素がすべて一意（重複なし）という条件が保証されています。この場合、A[i] − i の値は単調に増加するため、二分探索（バイナリサーチ）を使えば O(log n) まで高速化できます。

二分探索を使った実装例は次のようになります。

class Solution(object):
    def fixedPoint(self, A):
        left, right = 0, len(A) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if A[mid] == mid:
                result = mid
                right = mid - 1  # さらに小さいインデックスを探す
            elif A[mid] < mid:
                left = mid + 1   # 右半分を探索
            else:
                right = mid - 1  # 左半分を探索
        return result

データサイズが大きい場合や、同じ配列に対して複数回問い合わせを行うケースでは、二分探索版が大幅に効率的です。一方、小規模な配列であればシンプルな線形探索でも十分実用的です。