/*********************************************
	二分探索　Binary-Search
*********************************************/
import java.util.*;
public class Search02Binary {

	static int youso=10;
	static int[] num={6,9,19,33,45,49,55,65,70,98};
	static int answer;	// 探したい値
	static int flg;		// 探索フラグ　1:成功　0：不成功

// ------------ mainメソッド ------------	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		num_display();
		
		System.out.print("\n\n探したい値を入れて下さい-->");
		answer=sc.nextInt();
		flg=0;
		
		binary_search();  // 二分探索
		
		if ( flg==1 )
			System.out.print("\n見つかりました");
		else
			System.out.print("\nデータが見つかりません");
	}

// ------------ binary_searchメソッド ------------		
	static void binary_search() {
		System.out.print("\n----- Search START -----");
		int kagen,jogen,k;
		kagen=0;
		jogen=youso-1;

		while ( !( flg==1 || kagen>jogen ) ) {
			k=(kagen+jogen)/2;
			if ( answer== num[k] )
				flg=1;
			else if ( answer > num[k] )
				kagen=k+1;
			else
				jogen=k-1;
		}
		return;
	}
	

// ------------ num_displayメソッド ------------		
	static void num_display() {
		System.out.print(youso+"個の数字を探索します");
		System.out.print("（二分探索 Binary Search）\n");		
		for ( int i=0 ; i<=youso-1 ; i++ ) {
			System.out.print(num[i]+"　");
		}
		return;
	}
}