Number of Occurrences in Sorted Array in Swift

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

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