二分法查找

　

二分法查找

在用二分法查找前必须满足一个条件：必须是排序好的一组数字

思路：按照升序排序，从中间分，分成两半，如果所要查找的数字比中间的数字小，那么把后面一半不看（即相当于丢掉），然后查找前面一半，看所要查找的数字是否存在，按照上面的规律，把前面一半又分为一半，大大提高效率，如果找不到，那么返回-1。

下面是一个简单的例子：

import java.util.scanner;

/**
 * 测试二分法查找
 * @author AdMinistrator
 *
 */
public class Test01 {
	//二分法查找必须要有一个条件：必须是排序好的
	public static void main(String[] args) {
		int[] a = {0,1,2,3,4,5,6,7,8,9,10};
		Scanner s = new Scanner(System.in);
		int n = s.nextint();
		System.out.println(Search(a,n));
	}
	public static int Search(int[] a,int key) {
		int start = 0;
		int end = a.length - 1;
		while(start<=end) {
			int middle = (start+end)/2;
			if(key<a[middle]) {
				end = middle-1;
			}else if(key>a[middle]) {
				start = middle+1;
			}else {
				return middle;
			}
		}
		return -1;
	} 
}

相关阅读