Start learning free

LESSON 275 OF 415 · BINARY SEARCH

Number of Occurrences in a Sorted Array in Swift: O(log n)

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 occurrences of value.

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

We can find the first occurrence using an algorithm we have already studied: Lower Bound.
Can you write a similar binary search algorithm for finding the last occurrence 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 should we do if:
  • the element at index mid is greater than value?
  • the element at index mid is less than or equal to value?


  • If the element at index mid is greater than value, we should continue the search in the part of nums from left to mid - 1, e.g. set right to mid - 1
  • If the element at index mid is less than or equal to value, we should set ans to mid and continue the search in the part of nums from mid + 1 to right, e.g. set left to mid + 1

STEP 1 OF 10
    Ctrl + Enter to check

    SWIFT · BINARY SEARCH

    Number Of Occurrences in Swift, explained

    Problem overview

    The method count receives a sorted array of integers, nums, and a number value. It returns how many times value appears in the array. For nums = [1, 2, 2, 2, 4, 5] and value = 2 the answer is 3. The statement asks for O(log n) time and O(1) extra space, so walking through the array and counting is too slow.

    Approach: two lower bounds

    In a sorted array, equal values sit next to each other. The occurrences of value form one block of consecutive indices, and the answer is the length of that block. If the block starts at index low and ends just before index high, the count is high - low.

    Both borders come from the same tool, the lower bound: the index of the first element that is not less than a given number. It is found with a binary search in O(log n).

    • lowerBound(nums, value) is the index of the first occurrence of value, or the place where it would go if it were missing.
    • lowerBound(nums, value + 1) is the index of the first element greater than value. The array holds integers, so "not less than value + 1" means "greater than value".

    With the example, the first call returns 1 and the second returns 4, so the count is 4 - 1 = 3. If value is absent, both calls return the same index and the difference is 0, which is the right answer with no special case.

    Another way to see it: the first border says how many elements are strictly smaller than value, and the second says how many are smaller than or equal to it. Their difference is exactly the number of elements equal to value. The lower bound is a general tool, and the same helper answers questions such as how many elements are below a number.

    Step by step

    1. Get low. In count, declare a constant by calling lowerBound(nums, value).
    2. Get high. Call lowerBound(nums, value + 1). Every occurrence of value now sits at an index from low to high - 1.
    3. Return high - low.
    4. Write the helper above count as func lowerBound(_ nums: [Int], _ value: Int) -> Int.
    5. Declare left and right with var, set to 0 and nums.count - 1.
    6. Loop while left <= right, so a window of one element is still examined.
    7. Take the middle as (left + right) / 2, a let constant. Integer division rounds down to a valid index.
    8. If nums[middle] < value, set left = middle + 1: the lower bound must be further right.
    9. Otherwise set right = middle - 1: the element at middle is at least value, so the lower bound is there or to its left.
    10. Return left after the loop. It is the first index whose element is at least value, or nums.count if none is.

    The solution in Swift

    class Solution {
    func lowerBound(_ nums: [Int], _ value: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        while left <= right {
            let middle = (left + right) / 2
            if nums[middle] < value {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return left
    }

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

    The Swift details worth a closer look:

    • Methods call each other by bare name. Inside the class, count calls lowerBound directly, and the order of the two methods in the class does not matter.
    • The _ labels. Because the parameters are declared with _, calls have no labels: lowerBound(nums, value + 1).
    • A method named count. Arrays also have a count property, as in nums.count. They do not conflict: nums.count is the property of the array, while count(nums, value) is a method of Solution.
    • Overflow traps. value + 1 is ordinary Int arithmetic. For value equal to Int.max it would overflow and stop the program, because Swift does not wrap silently. For the values the lesson uses this cannot happen.

    Complexity

    A plain count with a loop would be correct but O(n); on a sorted array with millions of elements the two searches need only a few dozen comparisons.

    Time: O(log n). Each lowerBound call halves its window at every step, and count makes two calls, which is still O(log n).

    Space: O(1). Only a few integers are stored; the array is not copied.

    Edge cases and common mistakes

    • Value not present. For [1, 2, 2, 2, 4, 5] and 3, both lower bounds are 4, so the result is 0.
    • Empty array. The loop does not run, both calls return 0, and the result is 0.
    • Value at an end of the array. For [7, 7, 7] and 7 the bounds are 0 and 3, giving 3. The upper border may equal nums.count, and that is fine because it is only used in a subtraction.
    • Value outside the range of the array. For [1, 2] and 9, or for 0, the two bounds are equal and the answer is 0.
    • Finding one occurrence and walking outward. If the array is all one value, that walk is O(n). Two binary searches avoid it.
    • Using <= in the comparison. If the check were nums[middle] <= value, the search would find the border after the block, not before it, and both calls would return the same thing for many inputs.

    Testing

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