剑指offer-53

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

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

示例：

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

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

官方题解

class Solution:
    def search(self, nums, target: int) -> int:
        
        l,r = 0,len(nums)-1
        # 搜索有边界right,注意这里右边界取了等号

        while l <= r:
            mid = (l + r)//2
            if nums[mid] <= target: # 在右边界搜索
                l =  mid + 1
            else:
                r = mid -1 # 在左边界搜索
        right = l
        print(l,r)
        # 若数组中无 target ，则提前返回
        if r >= 0 and nums[r] != target:
            return 0
        
        
        # 搜索左边界left，注意这里右边界没有取等号
        l = 0
        while l <= r:
            m = (l+r)//2
            if nums[m] < target: # 在右区间查找
                l = m+1
            else:
                r = m -1 # 在左区间查找
        left = r
        return right - left - 1