Javaで配列内の要素を再帰的に線形検索するプログラムの書き方

本記事では、配列内の要素を再帰的な線形検索（リニアサーチ）で探す方法を、Javaのコード例とともに詳しく解説します。線形検索とは、配列の先頭から順番に要素を一つずつ比較していく、最もシンプルな探索アルゴリズムです。

以下に実行例を示します。

入力例と出力例

入力：

Input array:
14 20 35 47 50 65 72 81 90 99

Key element: 72

出力：

The element 72 is present at position: 6

このように、検索対象の値「72」が配列のインデックス6（7番目の位置）に見つかったことが分かります。

アルゴリズムの手順

Step 1 - 処理を開始する
Step 2 - 文字列型配列 input_array、整数型変数 key_element と index を宣言する
Step 3 - 各変数に値を設定する
Step 4 - 配列を走査する
Step 5 - 検索対象の要素を定義し、パラメータを渡して再帰メソッドを呼び出す
Step 6 - if文で条件判定を行い、見つからなければ -1 を返し、見つかればその位置を返す
Step 7 - 結果をコンソールに表示する
Step 8 - 処理を終了する

例1：整数型配列の線形検索

まずは、整数が格納された配列を対象にした線形検索の例です。

public class LinearSearch {
   static int recSearch(int input_array[], int l, int r, int key_element) {
      if (r < l)
         return -1;
      if (input_array[l] == key_element)
         return l;
      if (input_array[r] == key_element)
         return r;
      return recSearch(input_array, l+1, r-1, key_element);
   }
   public static void main(String[] args) {
      int input_array[] = {14, 20, 35, 47, 50, 65, 72, 81, 90, 99};
      System.out.println("The elements of the array is defined as ");
      for (int i : input_array) {
         System.out.print(i +" ");
      }
      int key_element = 72;
      System.out.println("

The elements to be searched in the array is: " + key_element);
      int index = recSearch(input_array, 0, input_array.length-1, key_element);
      if (index != -1)
         System.out.println("
The element " + key_element + " is present at position: " + index);
      else
         System.out.println("Element " + key_element + " is not present: ");
   }
}

実行結果

The elements of the array is defined as
14 20 35 47 50 65 72 81 90 99

The elements to be searched in the array is: 72

The element 72 is present at position: 6

コードのポイント

この再帰メソッド recSearch は、配列の両端（左端 l と右端 r）から同時に中央へ向かって探索範囲を狭めていきます。具体的な流れは以下の通りです。

• r < l になった場合、探索範囲が尽きたことを意味するため、-1（未発見）を返します。
• 左端または右端の要素が検索キーと一致すれば、そのインデックスを返します。
• 一致しなければ、l を1つ増やし、r を1つ減らして自身を再帰的に呼び出します。

この「両端から挟み込む」方式により、通常の片側からの再帰検索よりも再帰呼び出しの回数を約半分に抑えられるのが特徴です。

例2：文字列型配列の線形検索

次に、文字列が格納された配列を対象にした例を見てみましょう。

public class Demo {
   static int recSearch(String input_array[], int l, int r, String key_element) {
      if (r < l)
         return -1;
      if (input_array[l].equals(key_element))
         return l;
      if (input_array[r].equals(key_element))
         return r;
      return recSearch(input_array, l+1, r-1, key_element);
   }
   public static void main(String[] args) {
      String input_array[] = { "Scala", "Java", "Python", "Mysql"};
      System.out.println("The elements of the array is defined as ");
      for (String i : input_array) {
         System.out.print(i +" ");
      }
      String key_element = "Java";
      System.out.println("

The elements to be searched in the array is: " + key_element);
      int index = recSearch(input_array, 0, input_array.length-1, key_element);
      if (index != -1)
         System.out.println("
The element " + key_element + " is present at position: " + index);
      else
         System.out.println("Element " + key_element + " is not present: ");
   }
}

実行結果

The elements of the array is defined as
Scala Java Python Mysql

The elements to be searched in the array is: Java

The element Java is present at position: 1

文字列比較における注意点

文字列を比較する場合は、参照先が同一かどうかを判定する == 演算子ではなく、値そのものを比較する equals() メソッドを使用するのが安全です。上記の例では equals() を使うことで、文字列リテラル以外のオブジェクトが混在しても正しく動作するようになっています。

まとめ

この記事では、Javaを使って配列内の要素を再帰的に線形検索する方法を、整数型・文字列型の2つのサンプルで紹介しました。線形検索は計算量 O(n) のシンプルなアルゴリズムであり、小規模なデータやソートされていない配列の検索に適しています。再帰処理の基本構造を理解する練習としても最適なので、ぜひ実際にコードを動かしてみてください。