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

题目描述

描述转载自力扣 https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 与牛客题一致
统计一个数字在排序数组中出现的次数。

示例1

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

示例2

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

解题思路

1. 使用二分法找到数组中的 target；
2. 找到之后往前遍历数组，直到遍历到的值不等于 target；
3. 最后再往后遍历数组，每遍历到一个值就增加一次次数，直到遍历的值不等于 target。

Java代码实现

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 1 && nums[0] == target) return 1;
        // 二分查找
        int index = binSearch(nums, 0, nums.length - 1, target);
        // 如果没有找到对应的值，返回 0
        if (index == -1) return 0;
        // 因为找到的 index 的前面也可能有 target，所以往前遍历，找到数组中第一个与 target 相等的数
        while (index >= 0 && nums[index] == target) {
            --index;
        }
        ++index;
        int res = 0;
        // 从第一个 target 往后遍历，并增加次数，直到数组元素不等于 target
        while (index < nums.length && nums[index] == target) {
            ++res;
            ++index;
        }
        return res;
    }

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