在排序数组中查找数字 I

题目：

统计一个数字在排序数组中出现的次数，nums 是一个非递减数组。

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

思考：

提示

• 由排序的非递减数组，想到可以使用二分查找

• 求一个数字出现的次数，可以考虑找到这个数字的最左最右边界，即可计算出个数

• 因为得到的是最左边数字的前一个位置和最右数字的后一个位置，需要再减去 1

题解：

class Solution {
    public int search(int[] nums, int target) {

        // 搜索右边界 r
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int mid = (i + j) / 2;
            if(nums[mid] < target) i = mid + 1;
            else if (nums[mid] > target) j = mid - 1;
            else i++;
        }

        int r = i;

        // 搜索左边界 r
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int mid = (i + j) / 2;
            if(nums[mid] < target) i = mid + 1;
            else if (nums[mid] > target) j = mid - 1;
            else j--;
        }

        int l = j;

        return r - l - 1;
    }
}