Pythonでビトニックシーケンスのビトニックポイントを二分探索で効率的に求める方法

ビトニックシーケンス（Bitonic Sequence）とは、最初は厳密に増加し続け、ある一点を境にして厳密に減少していく数列のことです。この増加から減少へと切り替わる境界点のことを「ビトニックポイント」と呼びます。

例えば、入力が [7, 8, 9, 12, 10, 6, 3, 2] の場合、数列は 12 まで増加し、その後減少に転じるため、出力は 12 となります。なお、単調増加のみ、または単調減少のみの数列にはビトニックポイントは存在しません。

解法のアプローチ

ビトニックポイントを線形探索で見つけると計算量は O(n) になりますが、数列の性質を利用すると二分探索によって O(log n) まで高速化できます。手順は以下の通りです。

• 関数 binary_search(array, l, r) を定義します。
• l <= r の間、以下を繰り返します。
  • 中央インデックス m = (l + r) // 2 を求めます。
• array[m - 1] < array[m] かつ array[m] > array[m + 1] が成り立つ場合、m が山の頂点（ビトニックポイント）なので m を返します。
• array[m] < array[m + 1] の場合はまだ増加中なので、右半分 [m + 1, r] に対して再帰的に探索します。
• それ以外の場合はすでに減少に転じているので、左半分 [l, m - 1] に対して再帰的に探索します。
• 見つからなければ -1 を返します。

実装例

以下はPythonでの実装例です。

def binary_search(array, l, r):
    if (l <= r):
        m = (l + r) // 2;
        if (array[m - 1] < array[m] and array[m] > array[m + 1]):
            return m;
        if (array[m] < array[m + 1]):
            return binary_search(array, m + 1, r);
        else:
            return binary_search(array, l, m - 1);
    return -1;

array = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(array);
index = binary_search(array, 1, n-2);
if (index != -1):
    print(array[index]);

入力

[7, 8, 9, 12, 10, 6, 3, 2]

出力

12

計算量について

このアルゴリズムは各ステップで探索範囲が半分になるため、時間計算量は O(log n)、再帰呼び出しによる空間計算量も O(log n) となります。大きなビトニック配列からピーク要素を探す際に非常に効率的な手法です。