/**
     * 二分查找基础版-查找范围区间左闭右闭
     *
     * @param nums       待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回目标值的索引，找不到返回-1
     */
    public int search(int[] nums, int target) {
        // 设置指针 left 指向数组的开始索引位置
        int left = 0;
        // 设置指针 right 指向数组的最后索引位置
        int right = nums.length - 1;
        // 定一个 mid，表示 left 和 right 的中间索引位置
        int mid;
        /*
            对 [left,right] 范围内的元素进行查找，left <= right 成立说明在 [left,right] 范围内还有元素可以可以查找
            while循环退出的两种方式：
                - 进入了 else，说明找到了，返回中间索引
                - 不满足 left <= right，说明范围不断缩小后依旧没有找到，退出循环
         */
        while (left <= right) {
            // 查找中间索引，如果 (left+right)/2 为小数则会自动向下取整
            mid = (left + right) / 2;
            if (target < nums[mid]) {
                // 如果 目标值 小于 中间索引值，说明 目标值索引 应该在 中间索引 的左边
                // 我们可以通过调整 right 的值缩小查找范围
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 如果 目标值 大于 中间索引值，说明 目标值索引 应该在 中间索引 的右边
                // 我们可以通过调整 left 的值缩小查找范围
                left = mid + 1;
            } else {
                // 否则说明 目标值 等于 中间索引值，也就说明我们找到了
                return mid;
            }
        }
        // 走到这里说明没有进入过上面 while 中的else，while循环退出时 left > right
        // 说明没有找到
        return -1;
    }

/**
     * 二分查找基础版-查找范围区间左闭右开
     *
     * @param nums   待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回目标值的索引，找不到返回-1
     */
    public int search(int[] nums, int target) {
        // 设置指针 left 指向数组的开始索引位置
        int left = 0;
        // 设置指针 right 指向查找范围的后一个索引位置
        // 在这里 right 只是作为一个边界，指向的一定不是查找目标。
        int right = nums.length;
        int mid;
        // 在 [left,right) 左闭右开的区间范围内进行目标值查找
        // 因为 right 只是一个边界不作为查找索引，因此不能将 left <= right 作为条件
        while (left < right) {
            mid = (left + right) >>> 1;
            if (target < nums[mid]) {
                // 目标值 小于 中间索引值，则应该将右范围缩小
                // 需要将查找范围变为 [left,mid)
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

/**
     * <h3>二分查找平衡版</h3>
     *
     * <ol>
     *     <li>不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)</li>
     *     <li>i 指针可能是查找目标</li>
     *     <li>j 指针不可能是查找目标</li>
     *     <li>因为 1. 2. 3. 当区域内还剩一个元素时, 表示为 j - i == 1</li>
     *     <li>改变 i 边界时, m 可能就是目标, 同时因为 2. 所以有 i=m</li>
     *     <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 3. 所以有 j=m</li>
     *     <li>三分支改为二分支, 循环内比较次数减少</li>
     * </ol>
     *
     * @param nums      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
    public int search(int[] nums, int target) {
        int i = 0;
        int j = nums.length;
        // 范围内待查找的元素个数 > 1 时
        while (1 < j - i) {         
            int m = (i + j) >>> 1;
            if (target < nums[m]) {
                // 目标在左边，缩小右边范围
                j = m;
            } else {
                // 目标在 m 或右边
                i = m;
            }
        }
        return (target == nums[i]) ? i : -1;
    }

public int search(int[] nums, int target) {
        return recurSearch(nums, target, 0, nums.length-1);
    }
    private int recurSearch(int[] nums, int target, int left, int right) {
        // 说明全部搜索完毕仍未找到
        if (left > right) {
            return -1;
        }
        // 得到中间索引
        int mid = (left + right) >>> 1;
        // 比较目标值与中间索引对应值的大小
        if (target < nums[mid]) {
            // 如果目标值小于中间值
            right = mid - 1;
            return recurSearch(nums, target, left, right);
        } else if (nums[mid] < target) {
            // 如果目标值大于中间值
            left = mid + 1;
            return recurSearch(nums, target, left, right);
        } else {
            // 说明相等，则返回
            return mid;
        }
    }