一、题目内容

二、题解

解法1：

思路

两轮二分法查找。

代码

class Solution {
    public int search(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        // 搜索右边界 right
        while (i <= j) {
            int m = (j + i) / 2;
            if (nums[m] <= target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        //当前数组中无target
        if (j > 0 && nums[j] != target) {
            return 0;
        }
        //存储right
        int right = i;
        // 搜索左边界 right
        // 恢复i、j
        i = 0;
        j = nums.length - 1;
        while (i <= j) {
            int m = (j + i) / 2;
            //此处是 < 而不是 <=
            if (nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        int left = j;
        return right - left - 1;
    }
}

解法2：

思路

两轮二分法查找。
因为原数组为升序数组，则可以代码优化，转化为求 target与target-1的第一个右节点

代码

class Solution {
    public int search(int[] nums, int target) {
        return searchTargetRight(nums, target) - searchTargetRight(nums, target - 1);
    }
    public int searchTargetRight(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        // 搜索右边界 right
        while (i <= j) {
            int m = (j + i) / 2;
            if (nums[m] <= target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
}