【LeetCode刷题记录】剑指 Offer 53 - I. 在排序数组中查找数字 I（二分法）

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

输入: 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] 
要点1：
 
 
 
返回的边界应为：
 
 
[5,7,7,8,8,10]中
 
 
       ↑         ↑
 
 
而不是[5,7,7,8,8,10]
 
 
                     ↑ ↑
 
 
如果返回第二种的话，当只有一个元素时：
 
 
查找[1]中1的个数时返回的下标是同一个，得到的结果：1的个数为0
 
 
       ↑↑
 
 
 
 
要点2：
 
python中，在写包含递归的时if条件语句时，一定要写else，不然会返回None
 
要点3：
 
对于有序的数组, 都应该想到用二分法搜索
 
非递归的二分法写法：
 
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]