/**
 * 二分法基础
 * @param a             查找数组
 * @param target        查找目标值
 * @return              返回目标下标 or -1
 * 思路： 创建两个指针，分别指向数组两端，再使用一个中指针，
 * 用于判断目标值在中值的左侧还是右侧，然后再缩小范围，以此类推，可以缩小范围知道中值等于目标值
 */
static int binarySearch(int [] a,int target){
    // 定义左指针
    int i = 0;
    // 定义右指针
    int j = a.length-1;
    // 对左右指针的中值进行循环判断
    while (i<=j){
        // 取左右指针的中值， 向右移一位，或者除2
        int m = (i+j)>>>1;
        // 若中值小于目标值，说明值在中值右边
        if (a[m] < target){
            // 则将左指针移动到中值+1
            i = m+1;
            // 若中值大于目标值，说明目标值在中值左边
        } else if (a[m] > target) {
            // 则将右指针移动到中值-1
            j = m-1;
            // 当中值既不大于也不小于目标值，说明中值就是目标值
        } else {
            // 直接返回中值下标即可
            return m;
        }
    }
    return -1;
}

/**
 * 二分法改进版
 * @param a             查找数组
 * @param target        查找目标值
 * @return              返回数组下标 or -1
 * 思路： 创建两个指针，左右指针，右指针会溢出数组多一格
 * 右指针主要是为了区分边界值，右指针不会等于目标值，而左指针可能会等于目标值
 *
 */
static int basisSearch(int [] a, int target){
    // 定义左指针
    int i = 0 ;
    // 定义右指针，右指针会比数组长度多一格
    int j = a.length;
    // 循环遍历数组内，但左指针不等于右指针，因为右指针始终不会等于目标值，只当做边界值
    while (i<j){
        // 定义中值(中指针)
        int m = (i+j)>>>1;
        // 如果中指针小于目标值，则说明值在中指针右边，则将左指针移动到中值+1
        if (a[m]<target){
            i = m+1;
            // 如果中指针大于目标值，说明目标值在中指针坐标
        } else if (a[m] > target) {
            j=m;
        }else {
            return m;
        }
    }
    return -1;
}

/**
 * 线性查找(暴力查找)
 * @param a             待查找的数组
 * @param target        待查找目标值
 * @return              返回数组下标 or -1
 */
static int linerSearch(int [] a,int target){
    for (int i = 0; i < a.length; i++) {
        if (a[i]==target){
            return i;
        }
    }
    return -1;
}

public static void main(String[] args) {
    int [] a ={13,15,19,22,65};
    int target = 22;

    // 二分查找法 基础版
    int i = binarySearch(a, target);
    // 二分查找法 改进版
    int i1 = basisSearch(a, target);
    // 线性查找
    int i2 = linerSearch(a, target);
    System.out.println(i2);
}