Binary Search

Tag: LinkedIn

• http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/

Solution

1. Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.

2. Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.

3. Return (j – i + 1);

Time complexity O(logN)

public int count(int[] array, int target) {
    int i = findFirst(array, 0, array.length - 1, target);
    if (i == -1) return -1;

    int j = findLast(array, 0, array.length - 1, target);
    return j - i + 1;
}

private int findFirst(int[] array, int left, int right, int target) {
    if (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target && (mid == 0 || target > array[mid - 1])) { // if we find the first occurred element
            return mid;
        } else if (target > array[mid]) {
            return findFirst(array, mid + 1, right, target);
        } else {
            return findFirst(array, left, mid - 1, target);
        }
    } else {
        return -1;
    }
}

private int findLast(int[] array, int left, int right, int target) {
    if (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target && (mid == array.length - 1 || target < array[mid + 1])) { // if we find the first occurred element
            return mid;
        } else if (target < array[mid]) {
            return findLast(array, left, mid - 1, target);
        } else {
            return findLast(array, mid + 1, right, target);
        }
    } else {
        return -1;
    }
}