【剑指offer】 面试题53

题目描述

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

示例 1:

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

分析

1.暴力

2.有序数组优先考虑二分查找

找到target在数组中的起始位置

解题

class Solution:
    
    def search(self, nums: List[int], target: int) -> int:
        #二分找边界
        if (target not in nums) or (not nums):
            return 0
        l, r = 0, len(nums)-1
        # nums.sort()
        while l<r:
            mid = (l+r)//2
            if nums[mid] > target:
                r = mid
            elif nums[mid] < target:
                l = mid+1
            else:
                while nums[l]< target:
                    l+=1
                while nums[r]> target:
                    r-=1
                break
        return r-l+1