Решить задачу с помощью последовательного и двоичного поиска.
Найти N элементов массива, наиболее отдаленных от среднему арифметическому его максимального и минимального элементов.
Объясните мне дураку как решить этими поисками эту задачу
Найти N элементов массива, наиболее отдаленных от среднему арифметическому его максимального и минимального элементов.
Объясните мне дураку как решить этими поисками эту задачу
Последовательный поиск - это просто перебор. Сначала находишь среднее, потом сравниваешь с ним последовательно все элементы и смотришь, какой элемент от него больше всего отличется.
Двоичный поиск возможен только на отсортированном массиве, поэтому тут не возникает проблемы с поиском среднего арифметического. Алгоритм двоичного поиска описан очень много где, тебе надо его найти и просто подправить критерий поиска.
Если исходный массив отсортирован, то первые два требуемых элемента - это сами максимальный и минимальный, которые расположены на концах массива. Чтобы набрать оставшиеся, иди параллельно от начала и от конца, сравнивая модули разности текущих элементов со средним арифметическим (отдалённости) и добавляя тот, для которого отдалённость больше (и, соответственно, продвигаясь там на один элемент) . Когда наберётся нужное количество - выход.
Двоичный поиск сюда можно втиснуть так. Сравнив два элемента по отдалённости, двоичным поиском ищем элемент, отдалённость которого меньше отдалённости проигравшего элемента, но имеет тот же знак, что и отдалённость выигравшего элемента. Этот найденный элемент определяет границу диапазона, который надо включить в ответ. Сам найденный элемент в диапазон, конечно, не входит. То есть идея в том, чтобы продвигаться не на одну позицию, а сразу на несколько.
Если же исходный массив не отсортирован, то логичнее было бы определить минимальный и максимальный элементы, после чего просто отсортировать массив по убыванию отдалённости и взять первые Н элементов.