[5, 5, 8, 8, 8, 15, 23, 23]
If you use binary search algorithm to find the number 8 in the array, the algorithm may return index position 2, 3 or 4 depending on how the algorithm is implemented.
This article demonstrates two different implementations of the binary search algorithm in Java.
The first method returns the position of the first occurrence of an element in the array. While the second method returns the position of the last occurrence of the element in the array.
Binary Search to find the first occurrence of an element
This method uses the binary search algorithm to find an element in the sorted array. But unlike the normal binary search, this method doesn't stop when an element is found. Instead, it continues searching to the left of the array to find more elements. This is repeated until the array is exhausted.
If the search value does not exist in the array, then this method returns -1.
public static int binarySearchFirst(int a[], int searchValue){
int start = 0;
int end = a.length - 1;
int mid;
int result = -1;
while (start <= end) {
mid = (start + end) / 2;
// If searchValue found, continue searching left of the array.
if (a[mid] == searchValue) {
result = mid;
end = mid-1;
} else if (a[mid] > searchValue) {
end = mid - 1;
} else if (a[mid] < searchValue){
start = mid + 1;
}
}
// Return -1 if not found
return result;
}
Binary Search to find the last occurrence of an element
The algorithm to find the last occurrence of an element in the sorted array is very similar to finding the first occurrence. The only difference is after finding the first element, the search continues to the right side of the array, rather than the left.
public static int binarySearchLast(int a[], int searchValue){
int start = 0;
int end = a.length - 1;
int mid;
int result = -1;
// If searchValue found, continue searching right of the array.
while (start <= end) {
mid = (start + end) / 2;
if (a[mid] == searchValue){
result = mid;
start = mid+1;
} else if (a[mid] > searchValue) {
end = mid - 1;
} else if (a[mid] < searchValue){
start = mid + 1;
}
}
// Return -1 if not found
return result;
}
Binary Search to count the occurences of an element.
If you know the first and last positions of an element in the array, you could easily calculate the count of elements.
count = right - left + 1
For example, to count the number of occurrences of 8 in the array [5, 5, 8, 8, 8, 15, 23, 23], get the left and right positions of 8, which is 2 and 4 respectively. Therefore count of 8 is, 4 - 2 + 1 = 3
public static void main(String[] args) {
int[] my_array = {5, 5, 8, 8, 8, 15, 23, 23};
// Value to search
int target = 8;
// Call binarySearch method to get first position
int left = binarySearchFirst(my_array, target);
// Call binarySearch method to get Last position
int right = binarySearchLast(my_array, target);
// Calculate count
int count = right - left + 1;
System.out.println("The number "+ target + " occurs " + count + " times.");
}
Output
The number 8 occurs 3 times.
A second method and probably a more efficient one is to find the position of the first or last occurrence and then check its neighbouring elements to get the count.
int count = 0;
int left = binarySearchFirst(my_array, target);
int i = left;
while( i < my_array.length && my_array[i] == target){
count++;
i++;
}
Time complexity
The worst case time complexity of finding the first or last occurrence of an element is O(log n + k) where n is the number of elements in the array and k is the maximum number of occurences of any element in the array.
The worst case time complexity for finding number of occurrences is
Using first method:
O(2 (log n + k))
using second method.
O(log n + 2k)
