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


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


🐡 概要

binary-search-algorithm

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

🍄 特徴

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

🎂 AOJ問題

🗻 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

🖥 VULTRおすすめ

VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍