Binary search to find the occurrences of an element in a array

Posted on 22nd March 2021
The binary search algorithm is one of the most efficient algorithms used for searching an element in an array of sorted values. Consider an array of 8 integer values as below.

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

Post a comment

Comments

Nothing yet..be the first to share wisdom.