Бинарный поиск минимального и максимального элемента. Java
Мой метод находит под каким индексом стоит искомое число.
Мне нужно, чтобы он искал какое число присвоено минимальному индексу, а какое максимальному.
int position;
position = (first + last) / 2;
while ((array[position] != item) && (first <= last)) {
if (array[position] > item) {
last = position - 1;
} else {
first = position + 1;
}
position = (first + last) / 2;
}
if (first <= last) {
System.out.println(item + " является " + ++position + " элементом в массиве");
}
Ответы (1 шт):
Автор решения: Alex Rudenko
→ Ссылка
Только если входной массив отсортирован и содержит повторяющиеся элементы, то можно сначала бинарным поиском определить наличие искомого элемента, а затем можно искать индексы слева и справа.
В более общем случае несортированного входного массива проще отфильтровать индексы за O(N), и вернуть первый и последний индексы.
static int[] firstAndLastIndexes(int x, int ... arr) {
int[] indexes = IntStream.range(0, arr.length)
.filter(i -> arr[i] == x)
.toArray();
if (indexes.length < 1) {
return new int[]{-1, -1};
}
return new int[]{indexes[0], indexes[indexes.length - 1]};
}