53(1)-在排序数组中查找数字

统计一个数字在排序数组中出现的次数。

使用二分法来查询数字的左边界和右边界。

1234的左中位数是2，右中位数是3

public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int left = searchLeft(nums, target);//查询左边界
        int right = searchRight(nums, target);//查询右边界
        if (left == -1 || right == -1) {
            return 0;
        }
        return right - left + 1;
    }

    public int searchRight(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi +1) / 2;//取右中位数
            if (nums[mid] < target) { //如果中间数字小于target，说明下一次要从mid找，这里也可以是mid+1
                lo = mid;
            } else if (nums[mid] == target) { //如果中间数字等于target，说明可能是mid，从mid开始找。
                lo = mid;
            }else {
                hi = mid - 1; //如果中间数字大于target，说明下一次从mid-1开始，mid肯定不是。
            }
        }
        if (lo != nums.length && nums[lo] == target) {
            return lo;
        }
        return -1;
    }

    public int searchLeft(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;//取左中位数
            if (nums[mid] < target) {
                lo = mid + 1; //如果中间数字小于target，说明下一次要从mid+1开始找，nums[mid]一定不是target的最左边界
            } else if (nums[mid] == target) {
                hi = mid; //如果中间数字等于target，说明mid可能是target的最左边界
            }else {
                hi = mid;//这里也可以是hi = mid - 1;
            }
        }
        if (lo == nums.length) { //这里需要判断下是否越界
            return -1;
        }
        if (nums[lo] == target) { //确定一定是最左边界
            return lo;
        }
        return -1;
    }