新・明解Javaで学ぶアルゴリズムとデータ構造

戻る  

演習3-2の解答

   |   0   1   2   3   4   5   6
---+------------------------------
   |   *
  0|   6   4   3   2   1   9   8
   |
   |       * 
  1|   6   4   3   2   1   9   8
   |
   |           * 
  2|   6   4   3   2   1   9   8

その値はa[2]に存在します。

// 演習3-2
// 線形探索（探索過程の詳細を表示）

import java.util.Scanner;

class SeqSearchEx {

   //--- 配列aの先頭n個の要素からkeyと一致する要素を線形探索（番兵法）---//
   static int seqSearchEx(int[] a, int n, int key) {
      System.out.print("   |");
      for (int k = 0; k < n; k++)
         System.out.printf("%4d", k);
      System.out.println();

      System.out.print("---+");
      for (int k = 0; k < 4 * n + 2; k++)
         System.out.print("-");
      System.out.println();

      for (int i = 0; i < n; i++) {
         System.out.print("   |");
         System.out.printf(String.format("%%%ds*\n", (i * 4) + 3), "");
         System.out.printf("%3d|", i);
         for (int k = 0; k < n; k++)
            System.out.printf("%4d", a[k]);
         System.out.println("\n   |");
         if (a[i] == key)
            return i;         // 探索成功
      }
      return -1;               // 探索失敗
   }

   public static void main(String[] args) {
      Scanner stdIn = new Scanner(System.in);

      System.out.print("要素数：");
      int num = stdIn.nextInt();
      int[] x = new int[num];                  // 要素数numの配列

      for (int i = 0; i < num; i++) {
         System.out.print("x[" + i + "]：");
         x[i] = stdIn.nextInt();
      }

      System.out.print("探す値：");            // キー値の読込み
      int ky = stdIn.nextInt();

      int idx = seqSearchEx(x, num, ky);      // 配列xから値がkyの要素を探索

      if (idx == -1)
         System.out.println("その値の要素は存在しません。");
      else
         System.out.println("その値は" + "x[" + idx + "]にあります。");
   }
}

戻る