二分查找-037-数字在排序数组中出现的次数

题目描述

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

分析

在有序数组中的查找，二分查找具有时间复杂度上的优势。这里直接利用二分查找来分别查找目标值的左右边界来确定出现的次数，那么时间复杂度为O(logn)。

代码

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data:return 0
        
        left = self.GetLeftK(data, k)
        right = self.GetRightK(data, k)

        return right - left + 1 if left != -1 and right != -1 else 0
        
        
    def GetLeftK(self, data, k):
        left = 0
        right = len(data) - 1
        while left < right:
            mid = left + (right - left) // 2
            if data[mid] < k:
                left = mid + 1
            else:
                right = mid
        return left if data[left] == k else -1
        
    def GetRightK(self, data, k):
        left = 0
        right = len(data) - 1
        while left<right:
            mid = left + (right - left + 1) // 2
            if data[mid] > k:
                right = mid - 1
            else:
                left = mid
        return right if data[left] == k else -1