题目描述

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

难度简单119收藏分享切换为英文接收动态反馈

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

示例 1:

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

示例 2:

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

限制：

0 <= 数组长度 <= 50000

**注意：**本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

测试用例

• 功能测试（数组中包含要查找的数字；数组中没有要查找的数字；要查找的数字在数组中出现一次/多次）
• 边界值测试(查找数组中的最大值、最小值；数组中只有一个数字)
• 特殊输入测试（表示数组的指针为空指针）

题目考点

• 考察应聘者的只是迁移能力。
• 考察应聘者对二分查找算法的理解程度。

解题思路

一看到在排序数组中查找，大家一定能想到二分查找法，但是怎么用可以减少复杂度，that is problem.

1. 利用二分查找法找出最早(左)出现的k的下标
2. 利用二分查找法找出最晚(右)出现的k的下标

class Solution {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}