Title Description

Counts the number of times a number appears in a sorted array. For example, input the sorting array {1,2,3,3,3,4,5} and the number 3. Since 3 appears 4 times in this array, output 4

Problem solving ideas

Simple method

Because arrays are sorted, it is natural to think of using binary search. First use the binary search algorithm to find a 3, and then scan the left and right sides of the found 3 in order to find the first 3 and the last 3 respectively. Because the number to be searched may appear O(n) times in an array of length N, the time complexity of sequential scanning is O(n).

Thinking about how to make better use of binary search algorithm

Is it possible to find the first k and the last K directly with the binary search algorithm?

Compare the number in the middle of the array with K. if the number in the middle is larger than k, then K can only appear in the first half of the array. In the next round, you can only search in the first half of the array. The second half is the same.

If the middle number and K are equal, if the previous number is also K, then the first k must be in the first half of the array, and the next round of search is in the first half of the array.

Find the first k in the sorted array by recursion, and find the last K in the same way: if the middle number is smaller than k, K can only appear in the second half. If the middle number is equal to K, you need to judge whether this is the last K. Then the position of the last K - the position of the first k +1 is the number

Because the binary search method is used, the time complexity is O(logn)

Python code

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        num = 0
        if data and len(data) > 0:
            print("----")
            first = self.GetFirstK(data, k, 0, len(data)-1)
            last = self.GetLastK(data, k, 0, len(data)-1)
            print("1_first,end",first,last)
            if first > -1 and last > -1:
                print("first,end",first,last)
                num = last - first + 1
        return num
    
    def GetFirstK(self, data, k, start, end):
        if start > end:
            return -1
        middle_index = (start + end) // 2
        middle_data = data[middle_index]
        
        if( middle_data == k):
            if (middle_index > 0 and data[middle_index - 1] != k) or middle_index == 0:
                return middle_index
            else:
                end = middle_index - 1
        elif middle_data > k:
            end = middle_index - 1
        else:
            start = middle_index + 1
        return self.GetFirstK(data, k, start, end)
    
    def GetLastK(self, data, k, start, end):
        if start > end:
            return -1
        middle_index = (start + end) // 2
        middle_data = data[middle_index]
        
        if( middle_data == k):
            if (middle_index < len(data) - 1 and data[middle_index + 1] != k) or middle_index == len(data) -1:
                return middle_index
            else:
                start = middle_index + 1
        elif middle_data < k:
            start = middle_index + 1
        else:
            end = middle_index - 1
        return self.GetLastK(data, k, start, end)