/**
 * 
 */
package arithmetic;

/**
 * 二分查找, 要求：数据必须有序排列
 * 
 * 设数据量为N,复杂度为:log2(N)
 * 数据量翻倍时，复杂度加1，未翻倍时,倍数的临界会导致复杂度加1
 * 
 * @author zhangkexing
 *
 */
public class BinarySearch {
    
    int postion = -1;
    
    /**
     * 
     * @param array 原始数组
     * @param x 从数组中要查找的数字
     * @return 返回查找几次
     */
    public int binarySearch(int[] array,int x){
        int step = 0;
        int low = 0;
        int hight = array.length -1;
        
        while(low <= hight){
            ++ step;
            postion = (low + hight) /2;
            int data = array[postion];

            System.out.println("search:"+x+" postion:"+postion+" low:"+low+" hight:"+hight);
            if(data == x){
                return step;
            }else if(data > x){
                hight = postion - 1;
            }else{
                low = postion + 1;
            }
        }
        
        return -1;
    }
    public static void main(String[] args) {
        int len = 2049;
        int[] array = new int[len];
        for(int i=0;i<len;i++){
            array[i]=i;
        }
        
        int step = new BinarySearch().binarySearch(array, 70);
        if(step == -1){
            System.out.println("未查找到");
        }else{
            System.out.println("共执行"+ step+"次");
        }
    }
}