二分木探索 / Binary Search | アルゴリズム [AOJ ALDS1_4_A][Ruby/Java]

今回は、『探索 1 | アルゴリズムとデータ構造
』についての記事です。RubyとJavaのサンプルソースを載せています。

🎉 概要

整列済の集合に対して、対象の要素が見つかる(見つからない)まで、半分に集合を分割しながら検索する

🐹 特徴

線形探索の計算量がo(n) に対して、二分木探索の計算量はo(log(n)) となる
集まりがメモリに収まるなら、ハッシュにもとづいた探索のほうがよい

🐡 AOJ問題

探索 1 | アルゴリズムとデータ構造 | Aizu Online Judge

🗽 Javaコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int[] s = new int[n];
    String[] tmpS = br.readLine().split(" ");
    for(int i = 0; i < n; i++) {
      s[i] = Integer.parseInt(tmpS[i]);
    }
    tmpS = null;

    int q = Integer.parseInt(br.readLine());
    int[] t = new int[q];
    String[] tmpT = br.readLine().split(" ");
    for (int i = 0; i < q; i++) {
      t[i] = Integer.parseInt(tmpT[i]);
    }
    tmpT = null;

    int count = 0;
    for(int i : t) {
      if (binarySearch(s, i)) {
        count++;
      }
    }
    System.out.println(count);
  }

  private static boolean binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length;
    while (left < right) {
      int mid = (left + right) / 2;
      int temp = array[mid];
      if (target < temp) {
        right = mid;
        continue;
      }
      if (temp < target) {
        left = mid + 1;
        continue;
      }
      return true;
    }
    return false;
  }
}

😸 Rubyコード

def binary_search(arr, a)
  return false if arr.size <= 1 && arr.last != a
  mid = (arr.size/2).floor
  n = arr[mid]

  if a == n
    return true
  elsif a > n
    binary_search(arr[mid..-1], a)
  else
    binary_search(arr[0..mid-1], a)
  end
end

loop do
  n = gets.to_i
  break if n == 0

  arr = gets.split(' ').map(&:to_i).sort
  _q = gets.to_i
  q_arr = gets.split(' ').map(&:to_i)

  count = 0
  q_arr.each do |a|
    count += 1 if binary_search(arr, a)
  end
  puts count
end