我的任务是创建一个方法，该方法将打印在排序数组中找到值 x 的所有索引。
我知道如果我们只是从 0 到 N(数组长度)扫描数组，最坏情况下的运行时间为 O(n)。由于将对传递给该方法的数组进行排序，我假设我可以利用二进制搜索，因为这将是 O(log n)。但是，这仅在数组具有唯一值时才有效。由于二进制搜索将在第一次“找到”特定值后完成。我正在考虑进行二进制搜索以在排序的数组中找到 x，然后检查该索引前后的所有值，但是如果数组包含所有 x 值，它似乎并没有那么好。
我想我想问的是，有没有比 O(n) 更好的排序数组中特定值的所有索引的更好方法？
public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
// search through the sortedArrayOfInts
// print all indices where we find the number 42.
}
例如:sortedArray = { 1, 13, 42, 42, 42, 77, 78 } 会打印:“42 was found at Indices: 2, 3, 4”
您将在 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);
}
}
}