Pythonで配列内の最大要素のインデックスを見つけるプログラム

ここでは、「TestArray」というクラスが与えられていると想定します。このクラスは外部から直接アクセスできない非公開の配列を保持しており、length() と compare() という2つの公開メンバ関数を提供しています。

length() 関数は配列の長さを返します。一方、compare() 関数は l、r、x、y の4つの引数を受け取り、配列内の2つの部分区間の合計値を比較して、次の3種類の値を返します。

• (array[l] + array[l+1] + … + array[r]) > (array[x] + array[x+1] + … + array[y]) のとき：1 を返す
• 両者の合計が等しいとき：0 を返す
• (array[l] + … + array[r]) < (array[x] + … + array[y]) のとき：-1 を返す

今回の目的は、配列本体には一切アクセスせず、これらのメンバ関数だけを利用して、配列内の最大要素のインデックスを特定することです。

例として、入力が array = [8, 4, 2, 12, 11, 8, 4, 2, 7] の場合を考えてみましょう。この配列の最大要素は 12 であり、インデックス 3 の位置に存在するため、出力は 3 になります。

アルゴリズム：二分探索によるアプローチ

この問題は、二分探索の考え方を応用することで効率的に解けます。探索範囲を半分ずつに分割し、compare() を使って左右どちら側に最大要素が含まれるかを判定しながら、範囲を絞り込んでいくのがポイントです。具体的な手順は以下の通りです。

1. n := length() で配列の長さを取得する
2. low := 0、high := n - 1 と初期化する
3. low < high の間、次の処理を繰り返す：
   • mid := (low + high + 1) / 2 の切り捨て値とする
   • (low + high + 1) が偶数の場合：
     • res := compare(low, mid-1, mid, high)
     • res が 1 なら high := mid - 1
     • それ以外なら low := mid
   • (low + high + 1) が奇数の場合：
     • res := compare(low, mid-1, mid+1, high)
     • res が 1 なら high := mid - 1
     • res が -1 なら low := mid + 1
     • res が 0 なら最大要素は mid の位置にあるため、return mid
4. ループ終了後、high == low であれば return high
5. それ以外の場合は return -1

Pythonでの実装例

理解を深めるために、実際の実装を見てみましょう。

class TestArray:
    def __init__(self, array) -> None:
        self.__arr = array

    def length(self):
        return len(self.__arr)

    def compare(self, l, r, x, y):
        val1 = sum(i for i in self.__arr[l:r+1])
        val2 = sum(j for j in self.__arr[x:y+1])
        if val1 > val2:
            return 1
        elif val1 == val2:
            return 0
        elif val1 < val2:
            return -1

def solve(reader):
    n = reader.length()
    low, high = 0, n - 1
    while low < high:
        mid = (low + high + 1) // 2
        if (low + high + 1) % 2 == 0:
            res = reader.compare(low, mid - 1, mid, high)
            if res == 1:
                high = mid - 1
            else:
                low = mid
        else:
            res = reader.compare(low, mid - 1, mid + 1, high)
            if res == 1:
                high = mid - 1
            elif res == -1:
                low = mid + 1
            else:
                return mid
        if high == low:
            return high
    return -1

arr_ob = TestArray([8, 4, 2, 12, 11, 8, 4, 2, 7])
print(solve(arr_ob))

入力

[8, 4, 2, 12, 11, 8, 4, 2, 7]

出力

3

計算量について

このアルゴリズムでは、1回のループごとに探索範囲がほぼ半分になるため、compare() の呼び出し回数は O(log n) 程度に抑えられます。配列への直接アクセスが禁止されている特殊な状況でも、少ない比較回数で最大要素の位置を特定できるのが大きな魅力です。