算法--二分法查找

当我们需要从一个有序数组中查找是否存在某个值时，最简单的方法便是遍历数组，将需要查找的值与数组中每一个值进行比较。但这种方法的效率是非常低的，如果是长度为n的数组的话，则需要比较n-1次，而如果采用二分法查找，比较次数会大幅降低。

二分法查找适用于数据量较大时，但是数据需要先排好顺序。

主要思想

（设查找的数组区间为array[low, high]）

（1）确定该区间的中间位置K

（2）将查找的值T与array[k]比较。若相等，查找成功，返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：如果array[k]大于T ，由数组的有序性可知array[k,k+1,……,high]都大于T，故新的区间为array[low,……，K-1]；如果array[k]小于T 类似上面，查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。

（3）时间复杂度为:O(log2n)。

代码实现：

package com.demo;

import java.util.Scanner;

public class Demo {
	
	public static boolean seek(int key,int[] attr) {
		int i = 0;
		int j = attr.length - 1;
		int num = 0;

		while(i <= j) {
			num ++;
			int mid =  (i + j)/2;
			if (key < attr[mid]) j = mid - 1;
			else if (key > attr[mid]) i = mid + 1;
			else {
				System.out.println("共比较了" + num + "次");
				return true;
			}
		}
		System.out.println("共比较了" + num + "次");
		return false;
	}
	
	public static void main(String arg[]) { 
		
		System.out.println("请输入你需要的数组长度");
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] attr = new int[n];
		
		System.out.println("请输入" + n + "个有序数字");
		Scanner scan2 = new Scanner(System.in);
		for (int i = 0;i < attr.length;i++) {
			attr[i] = scan2.nextInt();
		}
		
		System.out.println("请输入要查找的数");
		Scanner scan3 = new Scanner(System.in);
		int key = scan3.nextInt();
		
		boolean b = seek(key,attr);
		if (b == true) {
			System.out.println("找到了");
		}else {
			System.out.println("没有找到");
		}
	}
}