⬅ Previous Topic
Last Occurrence in a Sorted ArrayNext Topic ⮕
Search Element in a Rotated Sorted Array⬅ Previous Topic
Last Occurrence in a Sorted ArrayNext Topic ⮕
Search Element in a Rotated Sorted ArrayTopic Contents
Given a sorted array of integers and a target number x
, your task is to count how many times the number x
appears in the array.
0
.0
.lastIndex - firstIndex + 1
.public class CountOccurrences {
public static int countOccurrences(int[] arr, int key) {
int first = findFirst(arr, key);
int last = findLast(arr, key);
if (first == -1 || last == -1) return 0;
return last - first + 1;
}
private static int findFirst(int[] arr, int key) {
int start = 0, end = arr.length - 1, res = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) {
res = mid;
end = mid - 1; // go left to find earlier occurrence
} else if (arr[mid] < key) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return res;
}
private static int findLast(int[] arr, int key) {
int start = 0, end = arr.length - 1, res = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) {
res = mid;
start = mid + 1; // go right to find later occurrence
} else if (arr[mid] < key) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 2, 3, 4};
int key = 2;
System.out.println("Count of " + key + ": " + countOccurrences(arr, key));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | If both first and last occurrences are found on the first try. |
Average Case | O(log n) | Binary search splits the array in half on each step, giving logarithmic performance. |
Worst Case | O(log n) | Both first and last searches may take log n steps independently. |
O(1)
Explanation: Only a few variables are used; no extra space is needed.
⬅ Previous Topic
Last Occurrence in a Sorted ArrayNext Topic ⮕
Search Element in a Rotated Sorted ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.