【C++】ソート済み配列から目標値に最も近い要素を検索する方法

n個の要素を持つソート済み配列Aがあるとします。この中から、指定された整数に最も近い値を見つけたいと思います。配列には重複した値や負の数が含まれている場合もあります。

例えば、配列が [2, 5, 6, 7, 8, 8, 9] で目標値が 4 の場合、最も近い要素は 5 となります。

解決のアプローチ

配列を先頭から順に走査し、各要素と目標値の絶対差を記録しておき、最後に差が最小となる要素を返すという線形探索の方法もあります。しかし、配列がすでにソートされているため、二分探索（バイナリサーチ）を使えば O(log n) の時間計算量でより効率的に解くことができます。

二分探索を用いた手順は以下の通りです。

• 目標値が先頭要素以下であれば、先頭要素をそのまま返す
• 目標値が末尾要素以上であれば、末尾要素をそのまま返す
• それ以外の場合は二分探索を行い、目標値が隣接する2つの要素の間に位置するとき、どちらの要素がより近いかを判定して返す

C++による実装例

#include<iostream>
#include<list>
using namespace std;

// 隣接する2つの値のうち、目標値に近い方を返す補助関数
int getNearest(int x, int y, int target) {
    if (target - x >= y - target)
        return y;
    else
        return x;
}

// 二分探索で最も近い要素を求める関数
int getNearestElement(int arr[], int n, int target) {
    if (target <= arr[0])
        return arr[0];
    if (target >= arr[n - 1])
        return arr[n - 1];

    int left = 0, right = n, mid = 0;
    while (left < right) {
        mid = (left + right) / 2;
        if (arr[mid] == target)
            return arr[mid];
        if (target < arr[mid]) {
            // 目標値が arr[mid-1] と arr[mid] の間にある場合
            if (mid > 0 && target > arr[mid - 1])
                return getNearest(arr[mid - 1], arr[mid], target);
            right = mid;
        } else {
            // 目標値が arr[mid] と arr[mid+1] の間にある場合
            if (mid < n - 1 && target < arr[mid + 1])
                return getNearest(arr[mid], arr[mid + 1], target);
            left = mid + 1;
        }
    }
    return arr[mid];
}

int main() {
    int arr[] = { 2, 5, 6, 7, 8, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 4;
    cout << "Nearest element of " << target << " is: " << getNearestElement(arr, n, target);
}

実行結果

Nearest element of 4 is: 5

このコードでは、まず目標値が配列の範囲外にないかを確認し、範囲内であれば二分探索によって候補を絞り込みます。目標値が2つの隣接要素の間に挟まれた時点で、補助関数 getNearest を使って距離が近い方の値を返す仕組みです。これにより、重複や負の数が含まれる配列でも正確に最も近い要素を高速に取得できます。