Binary Search is the one of the most simplest difficult algorithms in CS. The first Binary Search Algo was posted in 1946 and the first bug detection in the same happened in 1962. Currently, I have been working various forms of Binary Search Algos. and various applications of the same. One such interesting application is searching for frequency of any given element in a sorted array, which uses a slightly modified version of binary search. Most of the code I found online had minor bugs, so I decided to write my own in Java and post it for future reference.

Here is a basic algo of how you do this,

  • Step 1: Given a sorted array, we find the lowest index of the element in the array, let’s call it L.
  • Step 2: We find the highest index of the element in the array, let’s call it H.
  • Step 3:  We calculate the frequency by, H-L + 1.

Let’s break down these steps into more detailed analysis,

For Step 1, We start from the middle of an array and check for the following,

  1. If the current element is the element we are looking for AND the element to its LEFT is either different OR the current element is at 0th index, then the position of the current element becomes the lowest index.
  2. If above conditions are not met then we readjust our search domain within the array using binary search i.e. we check whether the current element is greater than or less than the element we are looking for.

For Step 2, We start from the middle of an array and check for the following,

  1. If the current element is the element we are looking for AND the element to its RIGHT is either different OR the current element is at highest index, then the position of the current element becomes the highest index.
  2. If above conditions are not met then we readjust our search domain within the array using binary search i.e. we check whether the current element is greater than or less than the element we are looking for.

Here’s the Java code for the same,

public static void main(String[] args) 
{
    doFrequencyAnalysis();
}

        private static void doFrequencyAnalysis() 
	{
		int arr[] = { 1, 3, 3, 3, 5, 5, 10 };
		int l = findLowestIndex(arr, 5, 0, arr.length - 1);
		int h = findHighestIndex(arr, 5, 0, arr.length - 1);

		// System.out.println("L = "+l+"H = "+h);

		if (l == -1) 
		{
			System.out.println("---------------::" + 0);
		} 
		else 
		{
			System.out.println("---------------::" + (h - l + 1));
		}

	}

        public static int findLowestIndex(int[] arr, int key, int low, 
			int high) 
	{
		int mid;

		while (low <= high) 
		{
			mid = (high + low) / 2;
			if ((mid == 0 || arr[mid - 1] != key) 
					&& arr[mid] == key) 
			{
				return mid;
			} 
			else if (arr[mid] >= key) 
			{
				high = mid;
			} 
			else 
			{
				low = mid;
			}
		}
		return -1;
	}

        public static int findHighestIndex(int[] arr, int key, 
			int low, int high) 
	{
		int mid;
		while (low <= high) 
		{
			mid = (high + low) / 2;
			if ((mid == arr.length - 1 || arr[mid + 1] != key) 
					&& arr[mid] == key) 
			{
				return mid;
			} 
			else if (arr[mid] <= key) 
			{
				low = mid;
			} 
			else 
			{
				high = mid;
			}
		}
		return -1;
	}

Binary Search helps us in accomplishing this task in log2N time, which makes us really appreciate its robustness.