Count Occurrences in a Sorted Array

1. Problem Description

Count how many times a number appears in a sorted array.

2. Approach

• Brute force
• Upper bound - lower bound: find the insertion positions for values slightly smaller and slightly larger than k, then subtract the positions

3. Implementation

3.1. Brute Force

// Brute force
// Time: O(N)
// Space: O(N)
func GetNumberOfK(data []int, k int) int {
	countMap := make(map[int]int, 0)
	for _, datum := range data {
		countMap[datum] ++
	}
	return countMap[k]
}

3.2. Upper Bound - Lower Bound

• java

public class 数字在排序数组中出现的次数
{
    public static void main(String[] args)
    {
        System.out.println(new 数字在排序数组中出现的次数().GetNumberOfK(new int[]{4, 3, 3, 3, 2, 1}, 3));
    }

    public int GetNumberOfK(int[] array, int k)
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            return 0;
        }
        // Binary-search the insertion position of k-0.5 as idx1
        int idx1 = this.getBinarySearchInsertIndex(array, k - 0.5);
        // Binary-search the insertion position of k+0.5 as idx2
        int idx2 = this.getBinarySearchInsertIndex(array, k + 0.5);

        // Return idx2-idx1
        return Math.abs(idx2 - idx1);

    }

    private int getBinarySearchInsertIndex(int[] array, double val)
    {
        int left = 0;
        int right = array.length - 1;
        // Ascending order
        if (array[left] < array[right])
        {
            while (left <= right)
            {
                int mid = (left + right) >>> 1;
                if (val < array[mid])
                {
                    right = mid - 1;
                }
                else if (val > array[mid])
                {
                    left = mid + 1;
                }
            }
        }
        // Descending order
        else
        {
            while (left <= right)
            {
                int mid = (left + right) >>> 1;
                if (val < array[mid])
                {
                    left = mid + 1;

                }
                else if (val > array[mid])
                {
                    right = mid - 1;

                }
            }
        }
        return left;
    }

}

• go

// Binary search
// Time complexity: O(logN)
// Space complexity: O(1)
func GetNumberOfK3(data []int, k int) int {
	right := UpperBinarySearch(data, k)
	left := LowerBinarySearch(data, k)
	return right - left - 1
}
func UpperBinarySearch(data []int, target int) int {
	left := 0
	// All values may be smaller than target, so initialize right to the array length to represent a missing boundary
	right := len(data)
	for left < right {
		mid := (left + right) / 2
		midValue := data[mid]
		// If the middle value <= target, all values on the left are <= target, so search on the right
		if midValue <= target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

func LowerBinarySearch(data []int, target int) int {
	// All values in the array may be greater than target, so initialize left to -1 to represent a missing boundary
	left := -1
	right := len(data) - 1
	for left < right {
		mid := left + (right-left+1)/2
		midValue := data[mid]
		// If the middle value < target, all values on the left are < target, so search on the right
		if midValue < target {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

4. References

• Count Occurrences in a Sorted Array - NowCoder
• Sword Offer 53-I. Find a Number in a Sorted Array - LeetCode