/****************************/
/* 二分探索とTreeSet */
/* coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;
// 探索
class Search
{
long tm1, tm2, tm3;
// 二分探索
int search(int key, int data[], int n)
{
int sw = 0, left = 0, right = n-1, center;
if (data[right] > data[left]) {
while (left < right) {
center = (left + right) / 2;
if (data[center] < key)
left = (center < n-1) ? center + 1 : center;
else
right = center;
}
}
else {
while (left < right) {
center = (left + right) / 2;
if (data[center] > key)
left = (center < n-1) ? center + 1 : center;
else
right = center;
}
}
if (data[left] == key)
sw = 1;
return sw;
}
// 配列と二分探索
void binary()
{
int i1, k, ct = 0, n = 0, s[] = new int [100000];
int data[] = new int [5000000];
Random rn = new Random((long)12345);
tm1 = System.currentTimeMillis();
for (i1 = 0; i1 < 5000000; i1++) {
k = rn.nextInt();
data[i1] = k;
ct++;
if (n < 100000) {
s[n] = k;
n++;
}
}
Arrays.sort(data);
tm2 = System.currentTimeMillis();
System.out.printf(" 保存： %d ms\n", tm2-tm1);
for (i1 = 0; i1 < n; i1++)
search(s[i1], data, 5000000);
tm3 = System.currentTimeMillis();
System.out.printf(" 探索： %d ms\n", tm3-tm2);
System.out.printf(" データ数： %d\n", ct);
}
// 配列と二分探索（binarySearch）
void binary_r()
{
int i1, k, ct = 0, n = 0, s[] = new int [100000];
int data[] = new int [5000000];
Random rn = new Random((long)12345);
tm1 = System.currentTimeMillis();
for (i1 = 0; i1 < 5000000; i1++) {
k = rn.nextInt();
data[i1] = k;
ct++;
if (n < 100000) {
s[n] = k;
n++;
}
}
Arrays.sort(data);
tm2 = System.currentTimeMillis();
System.out.printf(" 保存： %d ms\n", tm2-tm1);
for (i1 = 0; i1 < n; i1++)
Arrays.binarySearch(data, s[i1]);
tm3 = System.currentTimeMillis();
System.out.printf(" 探索： %d ms\n", tm3-tm2);
System.out.printf(" データ数： %d\n", ct);
}
// TreeSet
void binary_s()
{
int i1, k, ct = 0, n = 0, s[] = new int [100000];
Random rn = new Random((long)12345);
TreeSet<Integer> data = new TreeSet <Integer> ();
tm1 = System.currentTimeMillis();
for (i1 = 0; i1 < 5000000; i1++) {
k = rn.nextInt();
data.add(new Integer(k));
ct++;
if (n < 100000) {
s[n] = k;
n++;
}
}
tm2 = System.currentTimeMillis();
System.out.printf(" 保存： %d ms\n", tm2-tm1);
for (i1 = 0; i1 < n; i1++)
data.contains(s[i1]);
tm3 = System.currentTimeMillis();
System.out.printf(" 探索： %d ms\n", tm3-tm2);
System.out.printf(" データ数： %d\n", ct);
}
}
// main プログラム
public class Test
{
public static void main (String[] args)
{
Search ss = new Search();
// 配列と二分探索
System.out.printf("配列と二分探索\n");
ss.binary();
// 配列と二分探索（binarySearch）
System.out.printf("配列と二分探索（binarySearch）\n");
ss.binary_r();
// TreeSet
System.out.printf("TreeSet\n");
ss.binary_s();
}
}