13

11

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"

10Um, { 42, 13, 42, 12, 1, 0, 42 } is

notsorted. – Jon Skeet – 2012-11-02T14:49:55.607your solution sounds good, if the array contained all x values you would have to look at all of them anyway, no matter what – jlordo – 2012-11-02T14:52:42.450

@JonSkeet - Sorry about that typo. I've updated the array to a sorted one. – 5StringRyan – 2012-11-02T15:03:55.887

Possible duplicate of Finding multiple entries with binary search

– Elad Weiss – 2016-12-15T12:54:16.620