count_occurrences

CountOcc.java

public class CountOcc {

	private static int search(int array[], int low, int high, int value) {

		if (low <= high) {

			int mid = low + (high - low) / 2;

			if (array[mid] == value) {
				return mid;
			}

			else if (value < array[mid]) {

				return search(array, low, mid - 1, value);

			}

			else {

				return search(array, mid + 1, high, value);
			}

		}

		return -1;

	}

	private static int countOccurrences(int array[], int value) {
		int pos = search(array, 0, array.length - 1, value);

		int fo = pos, lo = pos;
		if (pos >= 0) {

			while (fo>=1 && array[fo] == array[fo - 1]) {

				fo = search(array, 0, fo - 1, value);

			}

			while (lo< array.length-1 && array[lo] == array[lo + 1]) {

				lo = search(array, lo + 1, array.length - 1, value);

			}
		}

		return lo - fo + 1;
	}

	public static void main(String args[]) {

		int array[] = { 1, 2, 3, 3, 3, 3, 4, 4,5, 5, 5, 5, 5, 5, 6 };

		int value = 4;
		
		int count = countOccurrences(array, value);

		System.out.println("Count : " +count);

	}

}