Start learning free

LESSON 246 OF 338 · BINARY SEARCH

Number of Occurrences in Go: O(log n) with Two Lower Bounds

Practice O(log n) Read the full explanation

Given a sorted array of integers nums, count the number of occurrences of a given value.

Example:

Input: nums = [1, 2, 2, 2, 4, 5], value = 2
Output: 3
Explanation: the value 2 appears 3 times in the array

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

Hints:

If value exists in nums, it will occur in a subarray of consecutive elements. If we manage to find this subarray, we'll also know the number of occurences of value.

This subarray is determined by the first and last indices where value occurs in nums. How would you find the first occurence in O(log n) time?

We can find the first occurence using an algorithm we have already studied: Lower Bound.
Can you write a similar binary search algorithm for finding the last occurence of value in nums?


We will implement a binary search and use a variable ans to store the best answer found so far, just like we did in Lower Bound. The only difference is how we handle the cases for each mid index. What shoud we do if:
  • a[mid] is greater than value?
  • a[mid] is less than or equal to value?


  • If a[mid] is greater than value, we should continue the search in nums[left...mid - 1], e.g. set right to mid - 1
  • If a[mid] is less than or equal to value, we should set ans to mid and continue the search in nums[mid + 1...right], e.g. set left to mid + 1

STEP 1 OF 10
    Ctrl + Enter to check

    GO · BINARY SEARCH

    Number Of Occurrences in Go, explained

    Problem overview

    The function count receives a sorted slice of integers, nums, and a value. It returns how many times value appears in nums. For nums = [1, 2, 2, 2, 4, 5] and value = 2 the answer is 3.

    The statement requires O(log n) time and O(1) extra space. A scan that counts matches is O(n), which is too slow, and so is a binary search that finds one match and then walks outward: with a slice made entirely of equal values that walk still takes O(n).

    Approach: where the equal elements start and where they end

    In a sorted slice all copies of value sit side by side. If you know the index where the block starts and the index just after where it ends, the count is the difference between the two.

    The lower bound of a value is the first index whose element is not smaller than it. So lowerBound(nums, value) is the start of the block of value (or the place where it would be inserted, if it is missing). Because the slice holds integers, the first element greater than value is the first element not smaller than value + 1, so lowerBound(nums, value+1) is the index just past the block.

    Both values come from one binary search each, so the whole function is two O(log n) searches. When value is absent, both calls return the same index and the difference is 0, so no special case is needed.

    For [1, 2, 2, 2, 4, 5] and value = 2: the first element not smaller than 2 is at index 1, and the first element not smaller than 3 is the 4 at index 4. The count is 4 - 1 = 3.

    Why does the lower bound loop find the start of the block rather than any element of it? Because it never stops on an equal element. When nums[middle] equals value, the loop treats it as "big enough" and keeps searching to the left, so it keeps squeezing toward the first copy. The same loop that finds an insert position therefore also finds the leftmost match, and calling it with value+1 turns "leftmost element at least value+1" into "first element after the block".

    Step by step

    1. Find the start. Declare low with := as lowerBound(nums, value).
    2. Find the end. Declare high as lowerBound(nums, value+1). Every copy of value sits at an index from low up to, but not including, high.
    3. Return the difference, high - low.
    4. Write the helper lowerBound(nums []int, value int) int below count. Go allows a function to call another one defined later in the file.
    5. Set the window with left, right := 0, len(nums)-1.
    6. Loop with for left <= right; Go has no while.
    7. Take the middle, (left + right) / 2.
    8. Smaller than value: everything up to middle is too small, so left = middle + 1.
    9. Otherwise: nums[middle] is at least value, so the boundary is at middle or to its left: right = middle - 1.
    10. Return left, the first index whose element is at least value, or len(nums) if there is none.

    The solution in Go

    func count(nums []int, value int) int {
    low := lowerBound(nums, value)
    high := lowerBound(nums, value+1)
    return high - low
}

func lowerBound(nums []int, value int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        middle := (left + right) / 2
        if nums[middle] < value {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return left
}

    Go details in this code

    • Function order doesn't matter. At package level, count may call lowerBound even though it is defined below it.
    • value+1 assumes integers. For floating-point numbers or strings there is no "next value", and a different second search would be needed. For int slices it is exact. (If value were the largest possible int, value+1 would wrap around, but the lesson's inputs are nowhere near that.)
    • Integer division truncates, and left + right never goes negative inside the loop, so middle is always a valid index.
    • The answer can be an index past the end. When value + 1 is larger than everything, high equals len(nums). It is only used in a subtraction, so that is fine.

    Trace lowerBound on [1, 2, 2, 2, 4, 5] with value = 2. At first left = 0 and right = 5, so middle = 2; nums[2] is 2, which is not smaller, so right = 1. Then middle = 0, nums[0] = 1 is smaller, so left = 1. Then middle = 1, nums[1] = 2, so right = 0. The loop ends with left = 1, the first 2.

    Complexity

    Time: O(log n). Each lowerBound call halves its window until it is empty, and the function makes two calls.

    Space: O(1). Just a few integers; the slice is passed by reference to its elements and never copied.

    Edge cases and common mistakes

    • Value missing. For [1, 2, 2, 2, 4, 5] and value = 3, both lower bounds are 4 and the result is 0.
    • Empty slice. Both lower bounds are 0, so the result is 0.
    • All elements equal. For [2, 2, 2] and value = 2, the lower bounds are 0 and 3, giving 3.
    • Value above everything or below everything. Both calls give the same index (the length or 0), so the count is 0.
    • Finding one match and walking. A plain binary search plus a linear walk is O(n) in the worst case.
    • Treating high as the last occurrence. It is one past the last occurrence; subtracting low already gives the count, with no + 1 needed.

    Testing

    • [1, 2, 2, 2, 4, 5], 2 gives 3.
    • [1, 2, 2, 2, 4, 5], 3 gives 0.
    • [2, 2, 2], 2 gives 3.
    • [], 1 gives 0.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free