C++プログラムで配列内の「不動点」（インデックスと等しい値）を見つける方法

このチュートリアルでは、次の問題を解決していきます。

与えられた配列の中から、その値がインデックス（添字）と一致する要素を探すという問題です。非常にシンプルな内容ですが、配列操作の基礎を学ぶのに最適な題材です。

解き方はシンプルで、配列を先頭から順番に走査し、配列の要素がそのインデックスと一致する箇所を見つけたら、そのインデックスを返すだけです。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int linearSearch(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        if(arr[i] == i) {
            return i;
        }
    }
    return -1;
}
int main() {
    int arr[] = {10, 20, 30, 40, 50, 5, 60};
    cout << linearSearch(arr, 7) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、以下の結果が得られます。

5

コードの解説

このプログラムでは線形探索を使用しています。配列 {10, 20, 30, 40, 50, 5, 60} の場合、インデックス5の位置にある値が5であるため、「5」が出力されます。該当する要素が存在しない場合は -1 を返す仕組みになっています。

計算量は O(n) となり、配列のサイズに比例して処理時間が増加します。なお、配列がソート済みの場合は二分探索を応用することで、O(log n) まで計算量を削減できる可能性があります。

まとめ

このチュートリアルについて不明な点や質問がある場合は、コメント欄でお気軽にお知らせください。