package chapter1;

/**
 * 二分查找
 * 算法思想:大问题切分为小问题,通过与区间中间位置的比较,使得查找范围每次折半.
 * 适用于数据量比较的场景,查询的范围必须是已排序的.
 * 时间复杂度:O(N) = log2(N)
 * **************
 * 0     N/2    N
 * -------------*
 * **************
 * N为数组长度,X为执行次数
 * N/2 = 2^X
 * X = log2(N)
 * @author liufq
 *
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};//数组必须是有序的
        System.out.println(bin(arr,1));
        System.out.println(bin(arr,-1));
        System.out.println(bin1(arr,1));
        System.out.println(bin1(arr,-1));
    }
    
    /**
     * 返回查找到的值得索引,如果查找不到返回-1
     * @param arr
     * @param value
     * @return
     */
    public static int bin(int[] arr, int value) {
        int left = 0;//查询区间的左边界
        int right = 0;//查询区间的右边界
        int mid;//边界的中间位置
        while(left!=right) {
            mid = (left+right)/2;
            if(value < arr[mid]) {
                right = mid;
            }else if(value > arr[mid]) {
                left = mid;
            }else {
                return mid;
            }
        }
        return -1;
    }
    
    /**
     * 递归实现
     * @param arr
     * @param value
     * @return
     */
    public static int bin1(int[] arr, int value) {
        return binRecursion(arr, value, 0, arr.length-1);
    }
    
    private static int binRecursion(int[] arr, int value, int left, int right) {
        if(left == right) {
            return -1;
        }
        int mid = (left+right)/2;
        if(value < arr[mid]) {
            return binRecursion(arr, value, left, mid);
        }else if(value > arr[mid]) {
            return binRecursion(arr, value, mid, right);
        }else {
            return mid;
        }
    }
}