C++でソート済み配列からk番目に欠落している要素を二分探索で求める方法

重複のない整数が昇順にソートされた配列Aが与えられたとき、配列の左端（先頭）の数を起点として、k番目に欠落している数を見つける問題を考えます。

例えば、配列が [4, 7, 9, 10] で k = 1 の場合、4と7の間で最初に欠けている数は 5 となります。

解法のアプローチ：二分探索

この問題は、単純に1つずつ数えていく線形探索でも解けますが、配列がソートされていることを利用すると二分探索によって O(log n) の時間計算量で効率的に解くことができます。

基本的な考え方は次の通りです。

• 区間 [low, high] 内に存在するはずの数の個数は「nums[high] − nums[low] + 1」個ですが、実際に配列に含まれるのは「high − low + 1」個です。
• その差「absent」が、その区間内で欠落している数の個数を表します。
• absent が k 以上であれば、答えは左半分の区間内にあるため探索範囲を狭めます。そうでなければ、k から absent を引いて右側へ進みます。

アルゴリズムの手順

• n を配列のサイズとし、low := 0、high := n − 1 と初期化します。
• もし nums[n − 1] − nums[0] + 1 − n < k ならば、配列全体の欠落数が k 未満であることを意味するので、
  nums[n − 1] + (k − (nums[n − 1] − nums[0] + 1 − n)) を返します。
• low < high − 1 の間、以下を繰り返します。
  • mid := low + (high − low) / 2
  • present := mid − low + 1（区間内の実際の要素数）
  • absent := nums[mid] − nums[low] + 1 − present（区間内の欠落数）
  • absent ≥ k なら high := mid、そうでなければ k から absent を減算し、low := mid とします。
• 最後に nums[low] + k を返します。

C++での実装例

以下に、上記のアルゴリズムを実装したC++コードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        int low = 0;
        int high = n - 1;
        if(nums[n - 1] - nums[0] + 1 - n < k) return nums[n - 1] + (k
        - ( nums[n - 1] - nums[0] + 1 - n)) ;
        while(low < high - 1){
            int mid = low + (high - low) / 2;
            int present = mid - low + 1;
            int absent = nums[mid] - nums[low] + 1 - present;
            if(absent >= k){
                high = mid;
            }else{
                k -= absent;
                low = mid;
            }
        }
        return nums[low] + k;
    }
};
main(){
    vector<int> v = {4,7,9,10};
    Solution ob;
    cout << (ob.missingElement(v, 1));
}

入力

[4,7,9,10]
1

出力

5

まとめ

このアルゴリズムでは、各ステップで探索範囲を半分に絞り込むため、時間計算量は O(log n)、空間計算量は O(1) となります。配列が非常に大きい場合や、k番目の欠落した数を高速に求めたい場合に特に有効な手法です。