/**
     * 使用二进制搜索算法在指定的整数数组中搜索指定的值。在进行此调用之前，必须对数组进行排序（按方法排序 sort(int[]) ）。
     * 如果未排序，则结果未定义。如果数组包含多个具有指定值的元素，则无法保证会找到哪个元素。
     * 参数：
   *    a – 要搜索的数组 
   *    key – 要搜索的值
   * 返回：搜索键的索引（如果它包含在数组中）;否则，（ -（插入点）-1）。
   * 插入点定义为将键插入数组的 点 ：第一个元素的索引大于键，如果数组中的所有元素都小于指定的键，则为 a.length 。
   * 请注意，这保证了当且仅当找到键时返回值将为 >= 0。
     */
    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
    // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];
            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

public static void main(String[] args) {
        // 二分查找目标值，不存在则插入
        /*
            原始数组：[2,5,8]
            查找目标值：4
            查询不到，返回的结果为 r = -待插入点索引-1
            在这里带插入点索引为 1，对应 r = -2
            那么我们分成这几步来进行拷贝：
                - 1.新建数组,大小为原数组的大小+1：         [0,0,0,0]
                - 2.将待插入点索引之前的数据放入新数组：     [2,0,0,0]
                - 3.将目标值放入到待插入点索引的位置：       [2,4,0,0]
                - 4.将原数组后面的数据都相继拷贝到新数组后面： [2,4,5,8]
         */
        // 定义原数组与目标值
        int[] oldArray = {2, 5, 8};
        int target = 4;
        // 搜索目标值4，没有找到，返回结果为 r =  -待插入点索引-1，这里的 r=-2
        int r = Arrays.binarySearch(oldArray, target);
        // r < 0 说明没有找到目标值，就插入
        if (r < 0) {
            // 获取待插入索引
            int insertIndex = -r - 1;
            // 1.新建数组,大小为原数组的大小+1
            int[] newArray = new int[oldArray.length + 1];
            // 2.将待插入点索引之前的数据放入新数组
            System.arraycopy(oldArray, 0, newArray, 0, insertIndex);
            // 3.将目标值放入到待插入点索引的位置
            newArray[insertIndex] = target;
            // 4.将原数组后面的数据都相继拷贝到新数组后面
            System.arraycopy(oldArray, insertIndex, newArray, insertIndex + 1, oldArray.length - insertIndex);
            System.out.println(Arrays.toString(newArray));
        }
    }

public static int binarySearchLeftmost(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        // 记录最小索引
        int minIndex = -1;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target < array[mid]) {
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] < target) {
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            } else {
                minIndex = mid;
                // 由于要查找最小索引，因此缩小右范围即可
                right = mid - 1;
            }
        }
        // 返回结果
        return minIndex;
    }

public static int binarySearchRightmost(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        // 记录最大索引
        int maxIndex = -1;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target < array[mid]) {
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] < target) {
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            } else {
                maxIndex = mid;
                // 由于要查找最大索引，因此缩小左范围即可
                left = mid + 1;
            }
        }
        // 返回结果
        return maxIndex;
    }

public static int binarySearchLeftmostFirst(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        // 记录最小索引
        int minIndex = -1;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target < array[mid]) {
                // array[mid] 满足大于目标值，因此可以记录
                minIndex = mid;
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] < target) {
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            } else {
                // array[mid] 满足等于目标值，因此可以记录
                minIndex = mid;
                // 由于要查找最小索引，因此缩小右范围即可
                right = mid - 1;
            }
        }
        // 返回结果，如果返回为-1说明没有找到，即数组所有元素都比目标值要小
        return minIndex;
    }

public static int binarySearchLeftmostSecond(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        // 记录最小索引
        int minIndex = -1;
        /*
            在 if 语句中，我们的操作是：
                1. 找到了 mid 索引，满足 array[mid] 大于等于目标值，
                2. 用 minIndex 记录这个大于等于目标值的索引，
                3. 然后将 mid -1 赋值给 right，也就是 (right + 1) 为当前找到的大于等于目标值的最小索引。
            if语句结束，就可以继续向前搜索看是否比当前 minIndex 更小的大于等于目标值的索引。
            在本次优化中，我们保证了：
                除非目标值大于数组元素的最大值，
                否则最终循环结束时的 (right + 1) 指针指向的一定是大于等于目标值的最小索引，
                也就是 minIndex = right + 1 。
            这个结论是后面的第二次优化的核心！！！
         */
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target <= array[mid]) {
                // array[mid] 满足大于等于目标值，因此可以记录
                minIndex = mid;
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] < target) {
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            }
        }
        // 返回结果
        return minIndex;
    }

public static int binarySearchLeftmostThird(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        /*
            在第一次优化中，我们保证了：
                除非目标值大于数组元素的最大值，
                否则最终循环结束时的 (right + 1) 指针指向的一定是大于等于目标值的最小索引，
                也就是最终 minIndex = right + 1 。
            while (left <= right) {
                mid = (left + right) >>> 1;
                if (target <= array[mid]) {
                    minIndex = mid;
                    right = mid - 1;
                } else if (array[mid] < target) {
                    left = mid + 1;
                }
            }
            我们再肯定一件事情：
                最终退出while循环的情况一定是 left > right 且 right + 1 = left 。
            而造成 left 比 right 多1，即 left 在 right 指针后面一位，一定是因为
                在以 left == right 为满足循环条件时，
                执行了if 语句中right左移 或者 else if语句中的left右移。
                我们之前又得到结论：最终循环结束时的 (right + 1) 指针指向的一定是大于等于目标值的最小索引。
                    - 当执行的是if语句中的right左移后，导致了新(right + 1)的值就是left，则left就是大于等于目标值的最小索引。
                    - 当执行的是else if语句中的left右移后，导致了left移动到了当前(right+1)指针的位置，则left就是大于等于目标值的最小索引。
             综上所述，我们发现：最终的left 指针就是那个大于等于目标值的最小索引，
             所以我们无需用 minIndex 进行记录，直接最终 return left 即可。
             那么这时候当目标值大于数组元素的最大值时，返回的left 就是 数组最大索引+1。
         */
        // 不需记录最小索引
        // int minIndex = -1;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target <= array[mid]) {
                // array[mid] 满足大于等于目标值，因此可以记录
                // minIndex = mid;
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] < target) {
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            }
        }
        // 返回结果
        return left;
    }

public static int binarySearchRightmostFirst(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        // 记录最小索引
        int minIndex = -1;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target < array[mid]) {
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] < target) {
                // array[mid] 满足小于目标值，因此可以记录
                minIndex = mid;
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            } else {
                // array[mid] 满足等于目标值，因此可以记录
                minIndex = mid;
                // 由于要查找最大索引，因此缩小左范围即可
                left = mid - 1;
            }
        }

public static int binarySearchRightmostSecond(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        // 记录最大索引
        int maxIndex = -1;
        /*
            在 else if 语句中，我们的操作是：
                1. 找到了 mid 索引，满足 array[mid] 小于等于目标值，
                2. 用 maxIndex 记录这个小于等于目标值的索引，
                3. 然后将 mid + 1 赋值给 left，也就是 (left - 1) 为当前找到的小于等于目标值的最大索引。
            else if语句结束，就可以继续向后搜索看是否比当前 maxIndex 更大的小于等于目标值的索引。
            在本次优化中，我们保证了：
                除非目标值小于数组元素的最小值，
                否则最终循环结束时的 (left - 1) 指针指向的一定是小于等于目标值的最大索引，
                也就是 maxIndex = left - 1 。
            这个结论是后面的第二次优化的核心！！！
         */
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target < array[mid]) {
                // 目标值小于中间索引值，缩小右范围
                right = mid - 1;
            } else if (array[mid] <= target) {
                // array[mid] 满足小于等于目标值，因此可以记录
                maxIndex = mid;
                // 目标值大于中间索引值，缩小左范围
                left = mid + 1;
            }
        }
        // 返回结果
        return maxIndex;
    }

public static int binarySearchRightmostThird(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        /*
            在第一次优化中，我们保证了：
                除非目标值小于数组元素的最小值，
                否则最终循环结束时的 (left - 1) 指针指向的一定是小于等于目标值的最大索引，
                也就是最终 maxIndex = left - 1 。
            while (left <= right) {
                mid = (left + right) >>> 1;
                if (target < array[mid]) {
                    right = mid - 1;
                } else if (array[mid] <= target) {
                    maxIndex = mid;
                    left = mid + 1;
                }
            }
            我们再肯定一件事情：
                最终退出while循环的情况一定是 left > right 且 right = left - 1。
            而造成 right 比 left 少1，即 right 在 left 指针前面一位，一定是因为
                在以 left == right 为满足循环条件时,
                执行了if 语句中right左移 或者 else if语句中的left右移。
                我们之前又得到结论：最终循环结束时的 (left - 1) 指针指向的一定是小于等于目标值的最大索引。
                    - 当执行的是if语句中的right左移后，导致了right移动到了当前(left - 1)的指针位置，则right就是小于等于目标值的最大索引。
                    - 当执行的是else if语句中的left右移后，导致了新(left-1)指针的位置就是当前right的位置，则right就是小于等于目标值的最大索引。
             综上所述，我们发现：最终的 right 指针就是那个小于等于目标值的最大索引，
             所以我们无需用 maxIndex 进行记录，直接最终 return right 即可。
             那么这时候当目标值小于数组元素的最小值时，返回的 right 就是 -1。
         */
        // 不需记录最小索引
        // int maxIndex = -1;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target < array[mid]) {
                right = mid - 1;
            } else if (array[mid] <= target) {
//                maxIndex = mid;
                left = mid + 1;
            }
        }
        // 返回结果，当然这个结果也可以写成 return left - 1
        return right;
    }