Question

Complete these 2 Java functions (the instructions are attached below):

private static int minIndexBinarySearch(int array[], int arrayLength, int key) {
// Complete this function.
}

private static int maxIndexBinarySearch(int array[], int arrayLength, int key) {
// Complete this function.
}

In certain applications, we are interested in counting the number of times key appears in a sorted array. The technique to solve such problems is to determine:
- minIndex: the minimum index where key appears
- maxIndex: the maximum index where key appears
The number of occurrences is given by (maxIndex - minIndex + 1).
Hence, our task is to find both the minimum and maximum positions where a key occurs. We seek to solve this using Binary Search. To this end, complete the following functions:
- int minIndexBinarySearch(int array[ ], int arrayLength, int key): returns the minimum index where key appears. If key does not appear, then returns -1.
- int maxIndexBinarySearch(int array[ ], int arrayLength, int key): returns the maximum index where key appears. If key does not appear, then returns -1.
Now, the countNumberOfKeys method returns the number of occurrences of key using the above two functions, and the formula above.
Caution: Your code should have complexity O(log n), where n = arrayLength. If your code ends up scanning the entire array (has a complexity O(n)), your work won't be counted.

Answer 1

class BinaryCounter { public static int firstIndex(int array[], int low, int high, int key, int arrayLength) { if (high >= low) { int mid = low + (high - low) / 2; //get mid element //found the firstIndex element if ((mid == 0 || key > array[mid - 1]) && array[mid] == key) { return mid; } //check in right else if (key > array[mid]) { return firstIndex(array, (mid + 1), high, key, arrayLength); } //check in left else { return firstIndex(array, low, (mid - 1), key, arrayLength); } } return -1; } public static int lastIndex(int array[], int low, int high, int key, int arrayLength) { if (high >= low) { int mid = low + (high - low) / 2; //found the last index of element if ((mid == arrayLength - 1 || key < array[mid + 1]) && array[mid] == key) { return mid; } //check in left else if (key < array[mid]) { return lastIndex(array, low, (mid - 1), key, arrayLength); } //check in right else { return lastIndex(array, (mid + 1), high, key, arrayLength); } } return -1; } static int minIndexBinarySearch(int array[], int arrayLength, int key) { return firstIndex(array, 0, arrayLength - 1, key, arrayLength); } static int maxIndexBinarySearch(int array[], int arrayLength, int key) { return lastIndex(array, 0, arrayLength - 1, key, arrayLength); } //count the number of keys static int countNumberOfKeys(int array[], int arrayLength, int key) { int maxIndex = maxIndexBinarySearch(array, arrayLength, key); //find last index int minIndex = minIndexBinarySearch(array, arrayLength, key); //find first index System.out.println("First Occurrence = " + minIndex); System.out.println("Last Occurrence = " + maxIndex); return maxIndex - minIndex + 1; //no of times occur } public static void main(String[] args) { int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; int n = arr.length; int x = 2; System.out.println("No of times occur = " + countNumberOfKeys(arr, n, x)); } }