UniLecs #Task. Наименьший и наибольший индекс
Задача: дан отсортированный по возрастанию массив целых чисел. Необходимо вернуть наименьший и наибольший индекс заданного элемента.
Входные данные: arr — массив целых чисел по модулю не больше 10⁵. Размер массива не более 10⁶.
Вывод: наибольший и наименьший индекс в массиве заданного элемента. Если такого элемента нет в массиве, выведите -1.
Пример:
Arr = [1, 2, 3, 4, 4, 4, 4, 7, 7, 9, 14]
1. Key = 1
Answer: MinIndex = 0, MaxIndex = 0.
2. Key = 4
Answer: MinIndex = 3, MaxIndex = 6.
Идея
Дан отсортированный массив и необходимо найти заданный элемент в массиве => просто напрашивается бинарный поиск. В нашем случае, нам необходимо найти два индекса — наименьший и наибольший, поэтому мы будем использовать бинарный поиск дважды, т.е. для каждого из индексов отдельно.
Классический алгоритм бинарного поиска
Для тех кто забыл, вот небольшое описание шагов бинарного поиска:
1. Определяем значение элемента в середине массива. Полученное значение сравнивается с исходным элементов (ключом).
2. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
3. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
4. Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
Кастомная модификация алгоритма бинарного поиска
Единственное, мы добавим разную логику для нахождения наименьшего и наибольшего индекса.
1. Для нахождения наименьшего индекса заданного элемента:
- На очередном шаге проверяем средний элемент с ключом: если он СТРОГО меньше ключа, то увеличиваем на единицу левую границу интервала, иначе уменьшаем на единицу правую границу интервала.2. Для нахождения наибольшего индекса заданного элемента:
- На очередном шаге проверяем средний элемент с ключом: если он МЕНЬШЕ ИЛИ РАВЕН ключу, то увеличиваем на единицу левую границу интервала, иначе уменьшаем на единицу правую границу интервала.
То есть, учитывая, что у нас есть дубликаты в массиве, то при нахождении наименьшего индекса заданного ключа, нам необходимо сдвигать интервал поиска влево, а при нахождениия наибольшего индекса — вправо.
Реализация
https://gist.github.com/unilecs/8da484ef37b6865f47c2dba0a39e837a
Play-test: https://dotnetfiddle.net/7mWlw9
