Using Binary Search with sorted Array with duplicates [duplicate]

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

You will get the result in O(lg n)

public static void PrintIndicesForValue(int[] numbers, int target) {     if (numbers == null)         return;      int low = 0, high = numbers.length - 1;     // get the start index of target number     int startIndex = -1;     while (low <= high) {         int mid = (high - low) / 2 + low;         if (numbers[mid] > target) {             high = mid - 1;         } else if (numbers[mid] == target) {             startIndex = mid;             high = mid - 1;         } else             low = mid + 1;     }      // get the end index of target number     int endIndex = -1;     low = 0;     high = numbers.length - 1;     while (low <= high) {         int mid = (high - low) / 2 + low;         if (numbers[mid] > target) {             high = mid - 1;         } else if (numbers[mid] == target) {             endIndex = mid;             low = mid + 1;         } else             low = mid + 1;     }      if (startIndex != -1 && endIndex != -1){         for(int i=0; i+startIndex<=endIndex;i++){             if(i>0)                 System.out.print(',');             System.out.print(i+startIndex);         }     } } 

Answer 2

Well, if you actually do have a sorted array, you can do a binary search until you find one of the indexes you're looking for, and from there, the rest should be easy to find since they're all next to each-other.

once you've found your first one, than you go find all the instances before it, and then all the instances after it.

Using that method you should get roughly O(lg(n)+k) where k is the number of occurrences of the value that you're searching for.

EDIT:

And, No, you will never be able to access all k values in anything less than O(k) time.

Second edit: so that I can feel as though I'm actually contributing something useful:

Instead of just searching for the first and last occurrences of X than you can do a binary search for the first occurence and a binary search for the last occurrence. which will result in O(lg(n)) total. once you've done that, you'll know that all the between indexes also contain X(assuming that it's sorted)

You can do this by searching checking if the value is equal to x , AND checking if the value to the left(or right depending on whether you're looking for the first occurrence or the last occurrence) is equal to x.