Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Count occurrences of a number in a sorted array with duplicates | Optimal Binary Search
    Data Structures & Algorithms

    Count occurrences of a number in a sorted array with duplicates | Optimal Binary Search

    codeanddebugBy codeanddebug3 July 2025No Comments4 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of question to find number of occurence in a sorted array
    Share
    Facebook Twitter LinkedIn Pinterest Email

    Given a sorted array, arr[] and a number target, you need to find the number of occurrences of target in arr[]. 

    Here’s the [Problem Link] to begin with.

    Examples :

    Input: arr[] = [1, 1, 2, 2, 2, 2, 3], target = 2
    Output: 4
    Explanation: target = 2 occurs 4 times in the given array so the output is 4.
    Input: arr[] = [1, 1, 2, 2, 2, 2, 3], target = 4
    Output: 0
    Explanation: target = 4 is not present in the given array so the output is 0.
    Input: arr[] = [8, 9, 10, 12, 12, 12], target = 12
    Output: 3
    Explanation: target = 12 occurs 3 times in the given array so the output is 3.

    Constraints:
    1 ≤ arr.size() ≤ 106
    1 ≤ arr[i] ≤ 106
    1 ≤ target ≤ 106

    Contents:
     [show]
    • Optimal Solution (Binary-Search Bounds)
      • Intuition & Approach
      • Code Implementation
      • Code Explanation
      • Dry Run (arr = [1, 2, 2, 2, 3], target = 2)
      • Time & Space Complexity
      • Conclusion

    Optimal Solution (Binary-Search Bounds)

    Intuition & Approach

    1. Lower Bound (lb) – index of the first element ≥ target.
    2. Upper Bound (ub) – index of the first element > target.
    3. The number of occurrences is simply ub – lb (length of the closed range holding target).
    4. If the lower-bound element isn’t actually target, then target never appears → count = 0.

    Code Implementation

    class Solution:
        # ---------- helper: first index with value >= target ----------
        def lower_bound(self, nums, target):
            n = len(nums)
            lb  = -1              # default when target isn't found
            low, high = 0, n - 1
    
            while low <= high:
                mid = (low + high) // 2
                if nums[mid] >= target:
                    lb  = mid          # potential first position
                    high = mid - 1     # keep searching left half
                else:                  # nums[mid] < target
                    low = mid + 1
            return lb
    
        # ---------- helper: first index with value > target ----------
        def upper_bound(self, nums, target):
            n = len(nums)
            ub  = n               # default when all elements <= target
            low, high = 0, n - 1
    
            while low <= high:
                mid = (low + high) // 2
                if nums[mid] > target:
                    ub  = mid          # potential upper bound
                    high = mid - 1     # look further left
                else:                  # nums[mid] <= target
                    low = mid + 1
            return ub
    
        # ---------- driver: count occurrences of target ----------
        def countFreq(self, arr, target):
            lb = self.lower_bound(arr, target)
            # if target never appears, quick exit
            if lb == -1 or arr[lb] != target:
                return 0
    
            ub = self.upper_bound(arr, target)
            return ub - lb            # total number of occurrences
    Python

    Code Explanation

    • lower_bound narrows leftward whenever it meets a value ≥ target, ensuring the final lb is the first such index—or -1 if no element is big enough.
    • upper_bound is identical except it searches for the first value strictly greater than target, returning n when everything is ≤ target.
    • Count logic:
      • If arr[lb] isn’t exactly target, the value doesn’t exist, so return 0.
      • Otherwise, every index from lb up to ub – 1 equals target, so the count is ub – lb.

    Dry Run (arr = [1, 2, 2, 2, 3], target = 2)

    1. Lower bound
      • Finds index 1 (first 2).
    2. Upper bound
      • Finds index 4 (first > 2, which is 3).
    3. Count = 4 – 1 = 3.

    Time & Space Complexity

    • Time: O(log n) – each bound is a binary search.
    • Space: O(1) – only a few integer variables.

    Conclusion

    By combining two small tweaks of binary search, you can count a value’s occurrences in a sorted array in logarithmic time, far faster than a linear scan, especially when the array is large. This pattern is a staple for frequency, range, and boundary problems on ordered data.

    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Array Binary Search
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleFind First and Last Position of Element in Sorted Array | Leetcode 34 | Optimal Binary Search
    Next Article Search in Rotated Sorted Array | Leetcode 33 | Optimal Binary Search
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Search in Rotated Sorted Array | Leetcode 33 | Optimal Binary Search

    3 July 2025
    Data Structures & Algorithms

    Find First and Last Position of Element in Sorted Array | Leetcode 34 | Optimal Binary Search

    2 July 2025
    Data Structures & Algorithms

    Ceil The Floor | Binary Search Implementation

    2 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (93)
      • Beginner (44)
      • Expert (22)
      • Intermediate (27)
    • Uncategorised (1)
    Recent Posts

    Search in Rotated Sorted Array | Leetcode 33 | Optimal Binary Search

    3 July 2025

    Count occurrences of a number in a sorted array with duplicates | Optimal Binary Search

    3 July 2025

    Find First and Last Position of Element in Sorted Array | Leetcode 34 | Optimal Binary Search

    2 July 2025

    Ceil The Floor | Binary Search Implementation

    2 July 2025

    Search Insert Position | Leetcode 35 | Explained in Python

    2 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.