Problem Link - Find Number of Occurrences in Binary Search
Problem Statement:
You are given a sorted array containing N integers and a number target. Complete the given function to find the number of occurrences of target in the given array.
Note: You need to solve this problem in O(log n) complexity.
Approach:
To find the number of occurrences of a target in a sorted array in O(log n) time, we can make use of binary search. We’ll break this task into two parts:
- Find the first occurrence of the target using binary search.
- Find the last occurrence of the target using binary search.
Once we know both the first and last occurrence indices, the number of occurrences of the target is simply the difference between these indices plus one.
Steps:
- For First Occurrence:
- Perform a binary search to find the first index where the target appears.
- Keep track of the index and move towards the left half to ensure it is the first occurrence.
- For Last Occurrence:
- Similarly, perform a binary search to find the last index where the target appears.
- Move towards the right half to ensure it is the last occurrence.
- Calculate Occurrences: Once the first and last occurrence indices are known, the number of occurrences is
last_occurrence - first_occurrence + 1. If the target is not found, return0.
Complexity:
- Time Complexity:
O(log n)Using Binary search - Space Complexity:
O(1)No extra space needed.