算法第四版的BinarySearch

package jichu;
/*
 * 一开始是正确的，搞错：最后的结果应该是排序后数组中的第几个，而不是在原来数组中的顺序。
 */
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import jxl.Cell;
import jxl.Sheet;
import jxl.Workbook;
import jxl.read.biff.BiffException;;

public class BinarySearch {

	public static void main(String[] args) throws IOException, BiffException  {
		
	    List whitelist = new ArrayList();
	    //使用txt方式存储
//		BufferedReader bf = new BufferedReader(new InputStreamReader(new FileInputStream("D://largeW.txt")));
//		String s = bf.readLine();
//		long t1 = System.currentTimeMillis();
//		while(s!=null){
//			whitelist.add((int)Integer.parseInt(s));
//			s = bf.readLine();
//		}
//		System.out.println(whitelist.size());
//		long t2 = System.currentTimeMillis();
//		System.out.println("running time is:"+(t2-t1)+"ms");
//		Collections.sort(whitelist);

		//使用excel方式存储  
	    //通过Workbook,Sheet,Cell这三个对象我们就可以实现Excel文件的读取工作。
	    //我们先想想一下读取步骤，不管是什么样的Excel操作框架必定都要经历 1.选取Excel文件得到工作薄 2.选择工作表 3.选择Cell 4.读取信息 
		Workbook rwb = Workbook.getWorkbook(new FileInputStream("D://largeW.xls"));//选取Excel文件得到工作薄Workbook 
		Sheet sheet = rwb.getSheet(0);//通过Workbook的getSheet方法选择第一个工作表（从0开始）
		int rows = sheet.getRows();
		int cols = sheet.getColumns();
		System.out.println("rows is:"+rows+" cols is:"+cols);
		long t1 = System.currentTimeMillis();
		for(int i = 0;i < rows;i++){
			Cell cell = sheet.getCell(0, i);//通过Sheet的getCell方法选择位置为C2的单元格(两个参数都从0开始) Cell c2 = sheet.getCell(2,1)
			String s = cell.getContents();//把单元格中的信息以字符的形式读取出来
			whitelist.add((int)Integer.parseInt(s));
		}
		long t2 = System.currentTimeMillis();
		System.out.println("running time is:"+(t2-t1)+"ms");
		Collections.sort(whitelist);
		long t3 = System.currentTimeMillis();
		System.out.println("sorting time is:"+(t3-t2)+"ms");
		for(Iterator it = whitelist.iterator();it.hasNext();){
			System.out.print(it.next()+" ");
		}
		Iterator it = whitelist.iterator();
		while(it.hasNext()){
			System.out.print(it.next()+" ");
		}
		
		
		System.out.println("input which to search:");
		Scanner scanner = new Scanner(System.in);
		int key = scanner.nextInt();
		int n = rank1(key,whitelist,0,whitelist.size()-1);
//		int r = rank1(key,a,0,a.length-1);
		
		System.out.println(key+" is the "+(n+1)+"th in the sorted list.");//加个()可以让n+1先计算 而不是把1认为成字符串。
	}

	public static int rank1(int key, List whitelist, int l, int h) {
		// TODO Auto-generated method stub
		int mid = 0;
		while(l <=  h){
			mid = (l + h) / 2;
			if(key > (int)whitelist.get(mid))      //全改成if的而不是if else的 函数会认为没有返回值，因为可能所有的if都不匹配，而if else一定会有一个匹配
				l = mid + 1;
			else if(key < (int)whitelist.get(mid))
				h = mid - 1;
			else return mid;
		}
		return -1;
	}

//	private static int rank(int key, List whitelist, int low, int high) {
//		// TODO Auto-generated method stub
////		System.out.println();
//		if(low > high)
//			return -1;
//		int mid = (low + high) / 2;
//		if(key > (int)whitelist.get(mid)) //全改成if的而不是if else的 函数会认为没有返回值，因为可能所有的if都不匹配，而if else一定会有一个匹配
//			return rank(key,whitelist,mid+1,high);
//		else if(key < (int)whitelist.get(mid))
//			return rank(key,whitelist,low,mid-1);
//		 else return mid;
//	}
}