C++でソート済み回転配列内の指定値以下の要素数をカウントする方法

整数の配列が与えられます。この配列は、昇順にソートされた配列をある位置で回転させたもの（ソート済み回転配列）です。ここでの目標は、配列に含まれる要素のうち、指定された値 K 以下であるものの個数を求めることです。

基本的なアプローチはとてもシンプルで、配列全体を一度走査しながら、K 以下の要素を順に数え上げるというものです。回転によって大小関係が崩れているため、通常の二分探索をそのまま適用することはできません。そこで、まずはこの線形走査による確実な方法を確認していきましょう。

入力例と出力例

例 1

Arr[] = { 1,2,3,4,9,8,10 } , K = 4

4 以下の要素の数 : 4

解説： 4 以下の要素は 1, 2, 3, 4 の 4 つなので、答えは 4 となります。

例 2

Arr[] = { 5,3,6,1,8,100,12,31 } , K = 3

3 以下の要素の数 : 2

解説： 3 以下の要素は 1, 3 の 2 つなので、答えは 2 となります。

プログラムで使用するアプローチ

• 整数配列 Arr[] に要素を格納し、比較対象となる値を K とします。
• 整数型の変数 n には配列の長さ（要素数）を格納します。
• 変数 count は「K 以下の要素の個数」を保持するためのカウンターです。
• 先頭要素（インデックス 0）から順に配列を一周します。
• 現在注目している要素が K 以下であれば、count を 1 増やします。
• 走査が完了した時点の count がそのまま求める答えになります。
• 最後に結果を出力します。

C++ 実装例

#include <iostream>
using namespace std;

int main(){
    int Arr[] = { 4,5,8,1,3,7,10,9,11 };
    int k = 7;
    int n = sizeof(Arr) / sizeof(Arr[0]);
    int count = 0;

    // 配列を先頭から走査し、k 以下の要素をカウント
    for(int i = 0; i < n; i++){
        if(Arr[i] <= k){
            count++;
        }
    }

    cout << "与えられたソート済み回転配列内の " << k << " 以下の要素の数 : " << count;
    return 0;
}

実行結果

与えられたソート済み回転配列内の 7 以下の要素の数 : 5

解説： 配列 { 4,5,8,1,3,7,10,9,11 } のうち、7 以下の要素は 4, 5, 1, 3, 7 の 5 つです。

計算量について

• 時間計算量： O(n) ― 配列の全要素を一度ずつ調べるため、要素数に比例した時間がかかります。
• 空間計算量： O(1) ― カウント用の変数以外に追加のメモリは不要です。

補足：さらに効率化できるケース

もし配列が回転されていない純粋なソート済み配列であれば、二分探索（upper_bound など）を使うことで O(log n) で答えを求められます。回転配列の場合でも、まず回転の基準点（ピボット）を特定できれば、分割後の各区間に対して二分探索を適用することで対数時間での求解も可能です。ただし、実装のシンプルさと安全性を優先するなら、本記事のように線形走査でカウントする方法が最も手軽で信頼できる選択肢といえるでしょう。