C++で二分探索により見つけられる要素の数を求める方法

問題概要

重複のない整数のリスト nums が与えられます。このリストの中から、標準的な二分探索（バイナリサーチ）の手順に従って実際に見つけ出せる整数が何個あるかを求めるのが課題です。

たとえば、入力が [2,6,4,3,10] の場合、出力は 3 になります。二分探索で 4 を探すと最初の反復で見つかり、2 と 10 は2回の反復後に見つかるためです。

解き方のアプローチ

この問題は、リスト内の各要素を「探索対象」として実際に二分探索を実行し、その探索が成功するかどうかを確認するというシンプルな方針で解けます。具体的には、以下の手順に従います。

• help() 関数を定義する：引数として探索対象の値 target と配列 nums を受け取ります。
• low := 0 と初期化します。
• high := nums のサイズ - 1 と初期化します。
• low <= high の間、以下を繰り返します。
  • mid := low + (high - low) / 2 を計算します。
  • nums[mid] が target と等しければ true を返します。
  • nums[mid] < target であれば low := mid + 1 とします。
  • それ以外の場合は high := mid - 1 とします。
• ループを抜けたら false を返します。

メイン処理の流れ

• 結果を格納する変数 ret := 0 を用意します。
• nums の各要素 i について ret := ret + help(i, nums) を実行します。
• 最後に ret を返します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool help(int target, vector<int> & nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target)
            return true;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
    int solve(vector<int> & nums) {
        int ret = 0;
        for (int i : nums) {
            ret += help(i, nums);
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<int> v = {2,6,4,3,10};
    cout << (ob.solve(v));
}

入力

{2,6,4,3,10}

出力

3

補足：計算量とポイント

1つの要素に対する二分探索の計算量は O(log n) であり、リスト内の全要素 n 個それぞれについて探索を行うため、全体の計算量は O(n log n) となります。

また、この問題の面白い点は、配列がソートされていなくても、二分探索の手順自体は機械的に進むため、偶然にも目的の値にたどり着くケースが存在することです。探索が成功するかどうかは、要素の配置と探索経路の組み合わせによって決まります。