package search;
import java.util.*;import java.io.*;
public class BinarySearch{ public static int times; /** recursion binarySearch */ public boolean recursionBinarySearch(Comparable[] data,int min,int max,Comparable target) { times++; boolean found = false; int midPoint = (min+max)/2; if (data[midPoint].compareTo(target) ==0) { found = true; } else if (data[midPoint].compareTo(target)>0) { if (min<= midPoint-1) found=binarySearch(data,min,midPoint-1,target); } else if (midPoint+1 <= max) { found = binarySearch(data,midPoint+1,max,target); } return found; } public resetTimes() { this.times = 0; } public boolean steadyBinarySearch(Comparable[] data,int min, int max,Comparable target) { times++; boolean found = false; int midPoint = (min+max)/2; while(min<max) { if (data[midPoint].compareTo(target) >0) max = midPoint; else low = midPoint; } if (data[min].compareTo(target) == 0) found = true; return found; } public static void main(String [] args) throws IOException { String inString ; StringTokenizer tokenizer; Integer [] elements; Comparable target; BinarySearch bs = new BinarySearch(); BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); //get size System.out.println("Please input the size ( size>0 ): "); inString = in.readLine(); elements = new Integer[Integer.parseInt(inString)]; //get data[] System.out.println("Enter the numbers of elements :(gap it with Key_space or Key_tab) "); inString = in.readLine(); tokenizer = new StringTokenizer(inString); for (int i =0; i<elements.length && tokenizer.hasMoreTokens();i++) { elements[i] = Integer.parseInt(tokenizer.nextToken()); } //get target System.out.println("Please input target element: "); inString = in.readLine(); target = new Integer(Integer.parseInt(inString)); long startTime = System.currentTimeMillis(); boolean found = bs.recursionBinarySearch(elements,0,elements.length-1,target); System.out.println("the result: "+found); System.out.println("take time = "+(System.currentTimeMillis()-startTime)); System.out.println("size : "+elements.length+" , cursory times : "+times); }}
