剑指 Offer 53 - I. 在排序数组中查找数字 I

题目链接：

力扣https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

【方法一】直接查找==target的num，统计次数

class Solution {

    int[] nums;
    int ans;
    int target;

    public void binary(int left, int right) {
        if(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                binary(mid + 1, right);
            }else if(nums[mid] > target){
                binary(left, mid - 1);
            }else{
                ans ++;
                binary(mid + 1, right);
                binary(left, mid - 1);
            }
        }
    }

    public int search(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        binary(0, nums.length - 1);
        return ans;
    }
}

【方法二】查找大于target的最小值下标和小于target的最大值下标，二者相减。这样就需要实现c++里的lower_bound和upper_bound。

class Solution {

    int[] nums;
    int target;
    
    public int lower_bound(int left, int right){
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        return right;
    }

    public int upper_bound(int left, int right){
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    public int search(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        return upper_bound(0, nums.length - 1) - lower_bound(0, nums.length - 1) - 1;
    }
}

lower_bound实现的小细节就是当target<=nums[mid]的时候继续向左找，right = mid -1，最后返回right