{1, 13, 27, 34, 38, 49, 49, 49, 49, 65, 76, 97, 101, 119} 当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到,比如这里的49。java代码
时间: 2023-07-27 10:21:33 浏览: 74
搜索一维数组中相同的值
以下是Java代码实现,使用了二分查找和遍历查找的组合方式:
```java
public static List<Integer> findAllOccurrences(int[] arr, int target) {
List<Integer> indexes = new ArrayList<>();
int left = 0, right = arr.length - 1;
// 二分查找第一个等于target的元素下标
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
int firstIndex = left;
// 如果数组中不存在目标值,则直接返回空列表
if (firstIndex >= arr.length || arr[firstIndex] != target) {
return indexes;
}
// 向左遍历查找所有相同的元素下标
for (int i = firstIndex; i >= 0 && arr[i] == target; i--) {
indexes.add(i);
}
// 向右遍历查找所有相同的元素下标
for (int i = firstIndex + 1; i < arr.length && arr[i] == target; i++) {
indexes.add(i);
}
return indexes;
}
```
你可以将数组和目标值作为参数传递给该方法,它会返回一个列表,包含了所有目标值在数组中的下标。例如,对于数组`{1, 13, 27, 34, 38, 49, 49, 49, 49, 65, 76, 97, 101, 119}`,如果要查找49这个值,可以调用该方法并传递数组和目标值:
```java
int[] arr = {1, 13, 27, 34, 38, 49, 49, 49, 49, 65, 76, 97, 101, 119};
int target = 49;
List<Integer> indexes = findAllOccurrences(arr, target);
System.out.println(indexes); // 输出 [5, 6, 7, 8]
```
阅读全文