Using Binary Search with sorted Array with duplica

Question

I've been tasked with creating a method that will print all the indices where value x is found in a sorted array.

I understand that if we just scanned through the array from 0 to N (length of array) it would have a running time of O(n) worst case. Since the array that will be passed into the method will be sorted, I'm assuming that I can take advantage of using a Binary Search since this will be O(log n). However, this only works if the array has unique values. Since the Binary Search will finish after the first "find" of a particular value. I was thinking of doing a Binary Search for finding x in the sorted array, and then checking all values before and after this index, but then if the array contained all x values, it doesn't seem like it would be that much better.

I guess what I'm asking is, is there a better way to find all the indices for a particular value in a sorted array that is better than O(n)?

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

Ex: sortedArray = { 1, 13, 42, 42, 42, 77, 78 } would print: "42 was found at Indices: 2, 3, 4"

Answer 1

public void printCopies(int[] array)
{
    HashMap<Integer, Integer> memberMap = new HashMap<Integer, Integer>();
    for(int i = 0; i < array.size; i++)
       if(!memberMap.contains(array[i]))
           memberMap.put(array[i], 1);
       else
       {
           int temp = memberMap.get(array[i]); //get the number of occurances
           memberMap.put(array[i], ++temp); //increment his occurance
       }

    //check keys which occured more than once
    //dump them in a ArrayList
    //return this ArrayList
 }

Alternatevely, instead of counting the number of occurances, you can put their indices in a arraylist and put that in the map instead of the count.

   HashMap<Integer, ArrayList<Integer>> 
   //the integer is the value, the arraylist a list of their indices

public void printCopies(int[] array)
{
    HashMap<Integer, ArrayList<Integer>> memberMap = new HashMap<Integer, ArrayList<Integer>>();
    for(int i = 0; i < array.size; i++)
       if(!memberMap.contains(array[i]))
       {
           ArrayList temp = new ArrayList();
           temp.add(i);
           memberMap.put(array[i], temp);
       }
       else
       {
           ArrayList temp = memberMap.get(array[i]); //get the lsit of indices
           temp.add(i);
           memberMap.put(array[i], temp); //update the index list
       }

    //check keys which return lists with length > 1
    //handle the result any way you want
 }

heh, i guess this will have to be posted.

 int predefinedDuplicate = //value here;
 int index = Arrays.binarySearch(array, predefinedDuplicate);
 int leftIndex, rightIndex;
 //search left
 for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it
 //leftIndex is now the first different element to the left of this duplicate number string
 for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it

 //right index contains the first different element to the right of the string
 //you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it
 for(int i = leftIndex+1; i<rightIndex; i++)
 System.out.println(array[i] + "\t");

Answer 2

A Hashmap might work, if you're not required to use a binary search.

Create a HashMap where the Key is the value itself, and then value is an array of indices where that value is in the array. Loop through your array, updating each array in the HashMap for each value.

Lookup time for the indices for each value will be ~ O(1), and creating the map itself will be ~ O(n).

Answer 3

Below is the java code which returns the range for which the search-key is spread in the given sorted array:

public static int doBinarySearchRec(int[] array, int start, int end, int n) {
    if (start > end) {
        return -1;
    }
    int mid = start + (end - start) / 2;

    if (n == array[mid]) {
        return mid;
    } else if (n < array[mid]) {
        return doBinarySearchRec(array, start, mid - 1, n);
    } else {
        return doBinarySearchRec(array, mid + 1, end, n);
    }
}

/**
 * Given a sorted array with duplicates and a number, find the range in the
 * form of (startIndex, endIndex) of that number. For example,
 * 
 * find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3
 * 3 10 10}, 6) should return (-1,-1). The array and the number of
 * duplicates can be large.
 * 
 */
public static int[] binarySearchArrayWithDup(int[] array, int n) {

    if (null == array) {
        return null;
    }
    int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n);
    int[] resultArray = { -1, -1 };
    if (firstMatch == -1) {
        return resultArray;
    }
    int leftMost = firstMatch;
    int rightMost = firstMatch;

    for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) {
        leftMost = result;
        result = doBinarySearchRec(array, 0, leftMost - 1, n);
    }

    for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) {
        rightMost = result;
        result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n);
    }

    resultArray[0] = leftMost;
    resultArray[1] = rightMost;

    return resultArray;
}

Answer 4

public void PrintIndicesForValue42(int[] sortedArrayOfInts) {
    int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42);
    while (left - 1 >= 0) {
        if (sortedArrayOfInts[left-1] == 42)
            left--;
    }
    while (right + 1 < sortedArrayOfInts.length) {
        if (sortedArrayOfInts[right+1] == 42)
            right++;
    }
    System.out.println("Indices are from: " + left + " to " + right);
}

This would run in O(log(n) + #occurrences) Read and understand the code. It's simple enough.