【Java】２分探索

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

この記事は探索アルゴリズムの2分探索についてまとめました。

2分探索

要素が昇順（もしくは降順）に並べられている配列において、探索範囲をほぼ半分ずつに減らしていきながら要素を探す探索アルゴリズムを2分探索(binary search)という。計算量は$\mathcal{O}(\log n)$。

2分探索の実装

この記事では要素が昇順に並べられた配列を想定しています。

Java

//--- 配列aの先頭n個の要素からKeyと一致する要素を2分探索する  ---//
/** 
 * @param a   :配列
 * @param n   :配列の要素数
 * @param key :探索する要素
 * @return 探索成功時:centerindx, 探索失敗時:-1
 */
static int binSearch(int[] a, int n, int key) {
  int leftidx  = 0;      // 探索範囲先頭index
  int rightidx = n - 1;  // 探索範囲末尾index
  
  do {
    int centeridx = (leftidx + rightidx) / 2; // 中央要素index
    
    if (a[centeridx] == key)
      return centeridx;
    else if (a[centeridx] < key)
      // 先頭indexを更新
      leftidx = centeridx + 1;
    else
      // 末尾indexを更新
      rightidx = centeridx - 1;
  } while (leftidx <= rightidx);
  return -1;
}

2分探索の利用例

Java

import java.util.Scanner;

public class BinarySearch {

  //--- 配列aの先頭n個の要素からKeyと一致する要素を2分探索する  ---//
  /** 
   * @param a   :配列
   * @param n   :配列の要素数
   * @param key :探索する要素
   * @return 探索成功時:centerindx, 探索失敗時:-1
   */
  static int binSearch(int[] a, int n, int key) {
    int leftidx = 0;       // 探索範囲先頭index
    int rightidx = n - 1;  // 探索範囲末尾index
    
    do {
      int centeridx = (leftidx + rightidx) / 2; // 中央要素index
      
      if (a[centeridx] == key)
        return centeridx;
      else if (a[centeridx] < key)
        // 先頭indexを更新
        leftidx = centeridx + 1;
      else
        // 末尾indexを更新
        rightidx = centeridx - 1;
    } while (leftidx <= rightidx);
    return -1;
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    //--- 配列aの用意 ---//
    System.out.println("【2分探索】");
    System.out.print("要素数:");
    int   num = stdIn.nextInt();
    int[] x   = new int[num];
    
    //--- 配列aに値を格納する ---//
    System.out.println("昇順に入力してください。");
    System.out.print("x[0];");
    x[0] = stdIn.nextInt();    // 先頭要素を格納
    
    for (int i = 1; i < num; i++) {
      // 一つ前の要素より小さければ再入力
      do {
        System.out.print("x[" + i + "]:");
        x[i] = stdIn.nextInt();
      } while (x[i] < x[i - 1]);
  }
    
    //--- 検索する要素を指定 ---//
    System.out.print("探す値:");
    int key = stdIn.nextInt();
    
    //--- 探索前の時刻を取得 ---//
    long startTime = System.currentTimeMillis();
    
    //--- ２分探索実行 ---//
    int idx = binSearch(x, num, key);
    
    //--- 探索後の時刻を取得 ---//
    long endTime = System.currentTimeMillis();
    
    //--- 探索結果の表示 ---//
    if (idx == -1)
      System.out.println("その値の要素は存在しません。");
    else
      System.out.println("その値はx[" + idx + "]にあります。");
    
    // 計測結果を表示
    System.out.println("処理時間:" + (endTime - startTime) + "ms");
  }
}

実行結果

【線形探索】
要素数:5
x[0]:9
x[1]:27
x[2]:48
x[3]:63
x[4]:81
探す値:9
その値はx[0]にあります。
処理時間:0ms

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。