二分查找

1. 设置一个起点索引和重点索引（length -1)
2. 使用右移计算中间值
3. 判断中间值向左移动还是向右

public class BinarySearch {

    /**
     * @param a      待查找升序数组
     * @param target 查找目标值
     * @return 查找目标索引，未找到返回-1
     */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;
        //循环内存在值
        //注意：一定是 <=，因为在最后一次的判断中当前位置也有可能是要查找的数值
        while (i <= j) {
            //中间索引
            //这里 /2 会有一个问题当target使用int最大数字的时候，第二次相加也就是m + 1的时候，
            //由于java会把高位当作无符号所以会出现负数，所以会出现问题
            //使用右移低位舍弃高位补0，运算结果不会产生印象
            //int m = (i + j) / 2;
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                //向左边移动
                j = m - 1;
            } else if (a[m] < target) {
                //向右边移动
                i = m + 1;
            } else {
                //当前就是
                return m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 15, 20};
        System.out.println(binarySearchBasic(a, 123));
    }

}

查找最左/右索引

引用场景，求排名

 /**
     * @param a      待查找升序数组
     * @param target 查找目标值
     * @return 查找目标索引，未找到返回-1
     */
    public static int findLeftBinarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;
        //候选者索引
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                //向左
                j = m - 1;
                //向右
//                i = m + 1;
            }
        }
        return candidate;
    }