Edit Question - KnowledgeHub

Title Body

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"

Tags (comma-separated) Cancel