【C++】単調増加数列における要素の位置を二分探索で検索する方法

概要

整数 l と、次の式で定義される単調増加数列が与えられた場面を考えます。

f(m) = am + bm[log₂(m)] + cm³

ここで、a = 1, 2, 3, …、b = 1, 2, 3, …、c = 0, 1, 2, 3, … です。記号 [log₂(m)] は「底を2とする対数を取り、小数点以下を切り捨てた値」を意味します。具体的には次のようになります。

• m = 1 のとき → 値は 0
• m = 2〜3 のとき → 値は 1
• m = 4〜7 のとき → 値は 2
• m = 8〜15 のとき → 値は 3

この問題の目的は、f(m) = l を満たす m を特定することです。もし l がこの数列に含まれない場合は 0 を出力します。

なお、扱う値はすべて 64 ビット整数で表現可能であり、3つの整数 a、b、c はいずれも 100 を超えないものとします。

入出力の例

例1

a = 2, b = 1, c = 1, l = 12168587437017

出力：

23001
f(23001) = 12168587437017

例2

a = 7, b = 3, c = 0, l = 119753085330

出力：

1234567890

解法のアプローチ

① 素朴な方法（線形探索）

与えられた a、b、c の値をもとに、m = 1 から順にすべての候補について f(m) を計算し、l と一致するかどうかを一つずつ比較していく方法です。実装は簡単ですが、計算量が O(N) になるため、m が大きくなると実行時間が膨大になります。

② 効率的な方法（二分探索）

f(m) は単調増加であるため、二分探索（バイナリサーチ）を適用できます。まず m の最小値 min と最大値 max を設定し、mid = (min + max) / 2 を評価しながら範囲を絞り込んでいきます。

• f(mid) < l の場合 → 探索範囲を大きい側へ移動する（min = mid + 1）
• f(mid) > l の場合 → 探索範囲を小さい側へ移動する（max = mid − 1）
• f(mid) = l の場合 → mid が求める答え

この手順を、目的の値が見つかるか、探索範囲がなくなるまで繰り返します。計算量は O(log N) に抑えられ、非常に高速に動作します。

探索範囲の上限について

探索範囲の設定には注意が必要です。c ≠ 0 の場合、m³ の項が支配的になるため、64 ビット整数の範囲内で m の最大値はおよそ 10⁶ となります。一方、c = 0 の場合は m が 10¹⁵ のオーダーまで達する可能性があるため、c の値に応じて探索範囲の上限を切り替える必要があります。

C++による実装例

// C++による実装例
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;

// a, b, c, m の各値に対する f(m) の値を返す関数
long long func(long long a1, long long b1, long long c1, long long m){
    long long res1 = a1 * m;
    long long logValue1 = floor(log2(m));
    res1 += b1 * m * logValue1;
    res1 += c1 * (m * m * m);
    return res1;
}

long long getPositionInSeries1(long long a1, long long b1,
    long long c1, long long l){
    long long start1 = 1, end1 = SMALL_N;
    // c が 0 の場合、m の値は 10^15 のオーダーになり得る。
    // c != 0 の場合、m^3 の項が 10^18 のオーダーになるため、
    // m の最大値は 10^6 となる。
    if (c1 == 0) {
        end1 = LARGE_N;
    }
    long long ans1 = 0;
    // 効率的な探索のために二分探索を実装
    while (start1 <= end1) {
        long long mid1 = (start1 + end1) / 2;
        long long val1 = func(a1, b1, c1, mid1);
        if (val1 == l) {
            ans1 = mid1;
            break;
        }
        else if (val1 > l) {
            end1 = mid1 - 1;
        }
        else {
            start1 = mid1 + 1;
        }
    }
    return ans1;
}

// ドライバーコード
int main(){
    long long a1 = 2, b1 = 1, c1 = 1;
    long long l = 12168587437017;
    cout << getPositionInSeries1(a1, b1, c1, l)<<endl;
    long long a2 = 7, b2 = 3, c2 = 0;
    long long l1 = 119753085330;
    cout << getPositionInSeries1(a2, b2, c2, l1)<<endl;
    long long a3 = 6, b3 = 2, c3 = 1;
    long long l2 = 11975309533;
    cout << getPositionInSeries1(a3, b3, c3, l2)<<endl;
    return 0;
}

出力

23001
1234567890
0

3つ目の例では、l = 11975309533 が a = 6、b = 2、c = 1 で定義される数列に含まれていないため、正しく 0 が出力されています。

まとめ

単調性を持つ数列から特定の値に対応する位置を見つける問題では、二分探索が最も効果的です。線形探索では O(N)、二分探索では O(log N) の計算量で済むため、m が 10¹⁵ オーダーの巨大な値になるケースでも現実的な時間で処理できます。また、c の値に応じて探索範囲の上限を適切に切り替えることで、64 ビット整数のオーバーフローを回避しながら正確な検索が可能になります。