Tbpgr Blog

Ruby プログラマ tbpgr(てぃーびー) のブログ

書籍 パーフェクトJava | 線形探索と二分探索

パンくず

書籍 パーフェクトJava
線形探索と二分探索

概要

Javaの線形探索と二分探索について

Javaの線形探索(リニアサーチ)と二分探索(バイナリサーチ

先頭から順次比較するような探索を線形探索、
真ん中の要素で分割しながら比較するような探索を二分探索といいます。

線形探索のサンプルコード

public class LinearSearch {

  public static void main(String[] args) {
    List<Integer> list = Arrays.asList(7,5,8,2,1,9,3,6,4,10);
    for (Integer element : list) {
      if (element.equals(5)) {
        System.out.println("hit!" + element);
      }
    }
  }
}

イナリサーチのサンプルコード

public class BinarySearch {

  public static void main(String[] args) {
    List<Integer> list = Arrays.asList(7, 5, 8, 2, 1, 9, 3, 6, 4, 10);

    Collections.sort(list);
    // 並び替えを確認 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    System.out.println(list);
    int index = Collections.binarySearch(list, 5);
    // 結果を確認 indexは4
    System.out.println(index);
    // 結果を確認 値は5
    System.out.println(list.get(index));
  }
}