『アルゴリズムとデータ構造』学習ノート：バイナリサーチ

javaのバイナリサーチ。これは書籍のほぼ丸写し。

import java.util.*;
import java.io.BufferedReader;

class BinarySearch {

  private static int binarySearch (int target, int[] numbers) {
    int left = 0;
    int right = numbers.length - 1;
    int center;

    while (left <= right) {
      center = (left + right) / 2;
      System.out.println("centrt: " + center);

      if (numbers[center] == target) {
        return center;
      }

      if (numbers[center] < target) {
        // centerより左側にtargetは存在しない
        left = center + 1;
      } else {
        // centerより右側にtargetは存在しない
        right = center - 1;
      }
    }

    // サーチ範囲がなくなっても一致するものがなかった場合
    return -1;
  }

  public static void main(String[] args) {

    // 数値を格納する配列の作成
    int[] numbers = new int[20];
    Random random = new Random();
    for (int i = 0; i < numbers.length; ++i) {
      numbers[i] = random.nextInt(10);
    }

    // 数値配列のソート
    Arrays.sort(numbers);

    // 数値配列の要素の出力
    for (int i = 0; i < numbers.length; ++i) {
      System.out.println(numbers[i]);
    }

    // 検索ワードのコマンドラインへの問いかけ
    System.out.println("\nWhat do you search for?");

    // コマンドラインからの入力値の受け取り
    int target = intReader();

    // バイナリサーチの実行
    int result = binarySearch(target, numbers);

    // 検索結果の出力
    if (result == -1) {
      System.out.println(target + "is not found...");
    } else {
      System.out.println(target + " is found at " + (result + 1));
    }
  }

  private static int intReader() {
    try {
      BufferedReader read = new BufferedReader(new java.io.InputStreamReader(System.in));
      String str = read.readLine();
      return Integer.parseInt(str);
    } catch (java.io.IOException e) {
      System.err.println("IO exception");
      return 0;
    } catch (NumberFormatException e) {
      return 0;
    }
  }
}

ruby版のバイナリサーチ。

# -*- coding: utf-8 -*-

# numbersは昇順にソート済みであることを前提とする
def binary_search(target, numbers)
  left = 0                   # 左端
  right = numbers.length - 1 # 右端
  center = nil                 # 中央値

  while left <= right do
    center = (left + right) / 2 
    puts center

    # 中央の値が検索対象であった場合
    if numbers[center] == target
      return center
    end 

    if numbers[center] < target
      # centerの値よりも大きい => centerより後（右）を探す
      # leftの値をcenter+1とし、検索対象を絞り込む
      left = center + 1 
    else
      # centerの値よりも小さい => centerより前（左）を探す
      # rightの値をcenter-1とし、検索対象を絞り込む
      right = center - 1 
    end 
  end 

  # 見つからなかった場合
  return -1
end

# 乱数を格納する配列を生成
numbers = []
20.times { numbers << rand(100) }

# 配列のソート
numbers.sort!

# 配列の出力
j = 0 
numbers.each do |number|
  puts "#{j} : #{number}"
  j = j + 1 
end

# 検索対象の問いかけ
puts "What do you search for?"

# コマンドラインからの入力の受け取り
target = STDIN.gets.chomp
#target = target.chomp

# バイナリサーチの実行
search_result = binary_search(target.to_i, numbers)

# 検索結果の出力
if search_result == -1
  puts "Could not found anything that matches \"#{target}\""
else
  puts "#{target} is found at #{search_result}"
end