Number of Occurrences in Sorted Array in O(log n) Time Using Java

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 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