🎯

【Java】線形探索

2024/02/28に公開

Java

初心者

tech

線形探索とは

探索アルゴリズムの中で、最も基本的でわかりやすいアルゴリズムです。
配列やリストなどの一列（線形）に並んだ要素を探索するもので、その探索方法は欲しい要素が見つかるまで先頭から1つずつチェックするものです。

線形探索のメリットとデメリット

メリット

単純で分かりやすい
実装が容易

デメリット

効率が悪く、処理速度が遅い
従って、要素数が増えたり、探索回数が増えるとパフォーマンスが落ちます。

今回の問題の内容と回答の方針等

問題
- サイズnの数列aのk番目に大きい値を探索せよ。
条件
- 入力値nとaとkは整数。
- nとkは、1以上10,000未満。
- 数列aの各要素の大きさは、マイナス10億以上プラス10億以下。
- 数列aの各要素の重複はないものとする。
解答方針
- 要素の数であるnは10,000未満なので、処理速度やメモリ使用量に問題がないため、線形探索で解く。
- 数列aは配列で管理。
- 答え（k番目に大きい値）を格納する変数maximumを用意して、入力の最大値より大きな値で初期化。
- maximum未満であり、かつ、数列aに含まれる最大値nextMaximumを求め、maximumをnextMaximumで更新することをk回繰り返す。
今回の入力値
上からn、a、kとする。
```
5
-9 10 6 0 -3
4
```

本問における線形探索のコード例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        // 入力を受け取る
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        
        // 答えを格納する変数 maximum に10億1を代入し初期化
        int maximum = 1000000001;
        
        // k回まわるループ処理
        for (int i = 0; i < k; i++) {
            
            // maximum 未満で数列に含まれる最大値を格納する変数 nextMaximum を用意してマイナス10億1で初期化
            int nextMaximum = -1000000001;
            
            // 配列の全要素をチェックするループ処理
            for (int value : a) {
                // 要素が maximum 未満かどうかの判定
                if (value < maximum) {
                	// 未満なら nextMaximum を更新
                    nextMaximum = Math.max(nextMaximum, value);
                }
            }
            // maximum を更新
            maximum = nextMaximum;
            
        }
        // 答えを出力する
        System.out.println(maximum);
    }
}

コード例の解説

Scanner sc = new Scanner(System.in);

入力値を受け取るためのおまじないを記述します。

int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = sc.nextInt();
}
int k = sc.nextInt();

入力値nを受け取ります。
配列aを宣言し、サイズをnとします。
n回ループするfor文を定義して、
配列aに入力値の2行目を全て代入します。
入力値kを受け取ります。

int maximum = 1000000001;

答えを格納する変数maximumを定義して、10億1を代入し初期化します。

for (int i = 0; i < k; i++) {
    int nextMaximum = -1000000001;

    for (int value : a) {
        if (value < maximum) {
            nextMaximum = Math.max(nextMaximum, value);
        }
    }
    maximum = nextMaximum;
}
System.out.println(maximum);

k回ループするfor文を定義して、
変数nextMaximumを定義して、マイナス10億1を代入して初期化します。
変数nextMaximumは、maximum未満、かつ、数列aに含まれる最大値を格納する変数です。
配列aの全要素を変数valueに順番に代入するfor文を定義して、
条件式が変数valueが変数maximum未満というif文を定義して、
条件式がtrueなら、変数nextMaximumと変数valueを比較して大きい方を、変数nextMaximumに代入して更新します。
3.のfor文を抜けたところで、変数maximumに変数nextMaximumを代入して更新します。
この変数maximumは、1回目のループで10となり、2回目で6となり、3回目で0となり、4回目のループで答えである-3となります。
1.のfor文を抜けたところで、変数maximumを出力します。

最も重要なこと

プログラムの最終目標はコードを書いて、理想の通り動くことです。言い方が悪いですが、理想通り動いてしまえばこっちのものです。
しかし、その後に待ち受ける手直しやアップデート等を考えると、可読性が良く、保守性が容易なコードを書くことが重要になってきます。
そのために、最も重要なことは解答方針をしっかり立てることです。 この解答方針が冗長なものだった場合、どんなに綺麗で効率の良いコードを書いても、出来上がるコードは冗長なものになってしまいます。
しかし、この解答方針を立てるという作業は、0から1を生み出す作業のため、基本的にはこれが最適解であるということが分かっていることはほぼありえません。
従って、よりベターな解答方針を立てるためには、様々なアルゴリズムに触れて、自分の引き出しを増やしておき、自分の実力を伸ばすことが必要になってきます。また、当然にコードを書く力も伸ばす必要があります。
私もこの記事を書いてる時点では、Javaの初心者です。様々なアルゴリズムに触れて、そして、コードを書く力も伸ばしている最中です。こればかりは一足飛びに上達する方法はなく、1つ1つコツコツやっていくしかありません。