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

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

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def dic_high(low,high):
            if low<=high:
                mid=int((low+high)/2)
                if nums[mid]==target:
                    return dic_high(mid+1,high)
                elif nums[mid]<target:
                    return dic_high(mid+1,high)
                else:
                    return dic_high(low,mid-1)
            else:
                return low
        def dic_low(low,high):
            if low<=high:
                mid=int((low+high)/2)
                if nums[mid]==target:
                    return dic_low(low,mid-1)
                elif nums[mid]<target:
                    return dic_low(mid+1,high)
                else:
                    return dic_low(low,mid-1)
            else:
                return high
        if nums:
            return dic_high(0,len(nums)-1)-dic_low(0,len(nums)-1)-1
        else: return 0
        


""" n=[1]
t=1
s=Solution()
val=s.search(n,t)
print(val) """

要点1：

返回的边界应为：

[5,7,7,8,8,10]中

       ↑         ↑

而不是[5,7,7,8,8,10]

                     ↑ ↑

如果返回第二种的话，当只有一个元素时：

查找[1]中1的个数时返回的下标是同一个，得到的结果：1的个数为0

       ↑↑

要点2：

python中，在写包含递归的时if条件语句时，一定要写else，不然会返回None

非递归的二分法写法：

class Solution(object):
    def search(self, nums, target):
        if nums:
            i=0
            j=len(nums)-1
            while i<=j:
                mid=(i+j)//2
                if nums[mid]<=target: i=mid+1
                else: j=mid-1
            h=i
            i=0
            while i<=j:
                mid=(i+j)//2
                if nums[mid]<target:
                    i=mid+1
                else:
                    j=mid-1
            l=j
            return h-l-1
        else:
            return 0


""" n=[-1,0]
t=0
s=Solution()
val=s.search(n,t)
print(val) """