Как найти медиану неотсортированного массива (без использования дополнительного массива)

@Дарья1997 · Регистрация: 05.10.2014

Студворк — интернет-сервис помощи студентам

как найти медиану неотсортированного массива, при этом не используя дополнительных массивов и не сортируя его.

@IrineK · 30.12.2014, 00:18

Без сортировки - никак.
По определению, медиана - это число, стоящее посредине отсортированной по возрастанию (убыванию) последовательности.

@Sacred6661 · 30.12.2014, 00:24

А массив целых чисел, дробов или чего?
IrineK права. Но в общем,если считать что медиана - это просто срееднее значение между минимальным и максимальным еллементами, то можно пытаться искать) Иначе ничего в голову не приходит)

@Дарья1997 · 30.12.2014, 00:29 **[ТС]**

В массиве содержится нечетное количество элементов 2n+1 элементов. Нужно найти n+1 по величине элемент, т.е. медиану массива и группу элементов с первыми n значениями, т.е. если бы массив был упорядочен, то этот элемент находился бы в центре. Найти этот элемент и левую половину. Вывести это на экран. Массив должен остаться в исходном состоянии. Минимальное использование количества памяти. Дополнительных массивов не используем.
вот сама задача,может я не так поняла

Добавлено через 1 минуту
да,действительно может попробовать найти сумму максимаьного и минимального элементов, а потом разделить его на 2 и искать число самое близкое к нему.

@SlavaSSU · 30.12.2014, 00:47

почему нельзя то? медиана - число, которое окажется посередине, если массив отсортировать.
медиану можно найти не сортируя массив.

просто переберем элемент, и проверим, что меньших чем он ровно столько, сколько надо. ну и там немножко помучиться с равными элементами.

@Дарья1997 · 30.12.2014, 01:07 **[ТС]**

то есть получается, что надо количество элементов меньших чем медиана равно количеству элементов больших медианы, и на основе этого условия надо совершать поиск медианы

@SlavaSSU · 30.12.2014, 01:11

если все элементы различны, то да. меньших и больштх должно быть ровно по n / 2.

@IrineK · 30.12.2014, 01:13

Сообщение от SlavaSSU

если все элементы различны

А если нет:
1 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5

@SlavaSSU · 30.12.2014, 01:14

IrineK, ну. меньших должно быть <= n / 2, а меньших + равных >= n / 2 + 1;

@IrineK · 30.12.2014, 01:18

А если они вообще double, как с ними бороться? )

@SlavaSSU · 30.12.2014, 01:22

а как бы вы боролись с этим, если бы можно было массив посортить? никак, верно, тупо взяли бы и написали sort(), ну и тут взять и писать знаки меньше и равно, вряд ли кто-то будет вводить силньо больше 2 знаков после запятой. ну а если будет, то, как обычно.

C++ (Qt)
1
2
3
const long double eps = 1e-15;
if(fabs(a - b) < eps))
// equal

@IrineK · 30.12.2014, 01:29

1) Находим минимум А и максимум В. Считаем среднее С = (А+В)/2
2) Проходим по массиву, считаем K - к-во чисел, <= С, и ищем М - наибольшее из чисел, меньших С.
Если K < n+1, то центр нужно сдвинуть вправо. A = М, B остается - переход на шаг 1)
Если K > n+1, то центр нужно сдвинуть влево. B = М, A остается - переход на шаг 1)
Если K == n+1, останов. Медиана найдена - это текущее М.

@SlavaSSU · 30.12.2014, 01:43

IrineK,
на тесте
5
1 1 1 1 1

остановится?

и еще этот алгоритм выдаст значение, которог нет в массиве.

3
1 100 101

выдаст 51, как я понимаю.

Добавлено через 12 минут
нет. вот тест
3
1 2 101
вот тут выдаст 51.

@IrineK · 30.12.2014, 01:47

Ну, подрихтовать можно.
Например ,в первом случае, можно отреагировать на min == max и просто написать ответ.

Во втором случае ответ будет 100,5.
Значит - вверху (пост 12) трохи исправила. И вроде выходит 100.

Ищите багу дальше.

Добавлено через 1 минуту
Третий:
1 2 101
A = 1 B = 101
C = 51
1, 2 M = 2
Даёт два, как положено.

@SlavaSSU · 30.12.2014, 01:51

IrineK,
3
1 2 2.

будет всегда приближаться к 2, но не достигнет.

он все таки достиг 2, я проверил. повезло. математически он не должен достигнуть 2.

а стоп. так он не остановится даже. всегда К будет равняться единице.

@IrineK · 30.12.2014, 02:01

Значит, ограничим число итераций, скажем, n+1.
И, если не удалось найти, мутим обратный ход - работаем во второй половине от максимума до середины.

A = 1 B = 2
C = 1.5
ищем те элементы, что больше, и минимальный из них
2, 2 М = 2 - это ответ

@SlavaSSU · 30.12.2014, 02:12

IrineK, кажись тут не работает теперь

5
1 1 2 2 3
1)A == 1, B == 3, C == 2, K == 2;
2)A == 2, B == 3, C == 2.5, K == 4,
3)A == 2, B == 2.5, C == 2.25, K == 4
.....
n + 1) A == 2, B == 2, K == 2. не нашлось. мутим обратно.
1)A == 1, B == 3, C == 2, K == 1;
2)A == 1, B == 2, C == 1.5, K == 4
3)A == 1.5, B == 2 C == 1.75, K == 4
и тут он опять приближается к двойке, только с другой стороны и K всегда равно 4, и в конце 1.
опять ничего не найдено.

@IrineK · 30.12.2014, 02:30

2n+1 = 5
1 1 2 2 3
A = 1 B = 3 C = 2
1,1,2,2 M = 2
A = 1 B = 2 C = 1.5
1,1 M = 1
cycled...

A = 1 B = 3 C = 2
2,2,3 M = 2 - END

Еще подрихтовала - ищем числа не строго меньше, а меньше-равно (от минимума до середины)
или
больше-равно (от середины до максимума).

Добавлено через 5 минут
2N+1 = 19
N = 9
1 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5
A = 1 B = 5 C = 3
1,3 M = 3
A = 3 B = 5 C = 4
1,3,4,4,4,4,4,4,4,4 M = 4 - здесь нужно еще среагировать на перебор за счет одинаковых элементов, т.к. по идее - здесь должен быть останов.

SlavaSSU, у вас код уже есть? )

@SlavaSSU · 30.12.2014, 02:31

IrineK, яне писал. но могу накатать, то что первым ответил ТСу.

@IrineK · 30.12.2014, 02:33

Поздно уже.

Продолжим завтра )

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Дарья1997 2 / 2 / 3 Регистрация: 05.10.2014 Сообщений: 209

	Как найти медиану неотсортированного массива (без использования дополнительного массива) 29.12.2014, 23:59. Показов 20781. Ответов 30 Метки нет (Все метки) как найти медиану неотсортированного массива, при этом не используя дополнительных массивов и не сортируя его. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 00:18
	Без сортировки - никак. По определению, медиана - это число, стоящее посредине отсортированной по возрастанию (убыванию) последовательности. 0

@Sacred6661 99 / 81 / 93 Регистрация: 03.12.2013 Сообщений: 217
	30.12.2014, 00:24
	А массив целых чисел, дробов или чего? IrineK права. Но в общем,если считать что медиана - это просто срееднее значение между минимальным и максимальным еллементами, то можно пытаться искать) Иначе ничего в голову не приходит) 0

@Дарья1997 2 / 2 / 3 Регистрация: 05.10.2014 Сообщений: 209
	30.12.2014, 00:29 [ТС]
	В массиве содержится нечетное количество элементов 2n+1 элементов. Нужно найти n+1 по величине элемент, т.е. медиану массива и группу элементов с первыми n значениями, т.е. если бы массив был упорядочен, то этот элемент находился бы в центре. Найти этот элемент и левую половину. Вывести это на экран. Массив должен остаться в исходном состоянии. Минимальное использование количества памяти. Дополнительных массивов не используем. вот сама задача,может я не так поняла Добавлено через 1 минуту да,действительно может попробовать найти сумму максимаьного и минимального элементов, а потом разделить его на 2 и искать число самое близкое к нему. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 00:47
	почему нельзя то? медиана - число, которое окажется посередине, если массив отсортировать. медиану можно найти не сортируя массив. просто переберем элемент, и проверим, что меньших чем он ровно столько, сколько надо. ну и там немножко помучиться с равными элементами. 0

@Дарья1997 2 / 2 / 3 Регистрация: 05.10.2014 Сообщений: 209
	30.12.2014, 01:07 [ТС]
	то есть получается, что надо количество элементов меньших чем медиана равно количеству элементов больших медианы, и на основе этого условия надо совершать поиск медианы 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 01:11
	если все элементы различны, то да. меньших и больштх должно быть ровно по n / 2. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 01:14
	IrineK, ну. меньших должно быть <= n / 2, а меньших + равных >= n / 2 + 1; 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 01:18
	А если они вообще double, как с ними бороться? ) 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 01:29
	1) Находим минимум А и максимум В. Считаем среднее С = (А+В)/2 2) Проходим по массиву, считаем K - к-во чисел, <= С, и ищем М - наибольшее из чисел, меньших С. Если K < n+1, то центр нужно сдвинуть вправо. A = М, B остается - переход на шаг 1) Если K > n+1, то центр нужно сдвинуть влево. B = М, A остается - переход на шаг 1) Если K == n+1, останов. Медиана найдена - это текущее М. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 01:43
	IrineK, на тесте 5 1 1 1 1 1 остановится? и еще этот алгоритм выдаст значение, которог нет в массиве. 3 1 100 101 выдаст 51, как я понимаю. Добавлено через 12 минут нет. вот тест 3 1 2 101 вот тут выдаст 51. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 01:47
	Ну, подрихтовать можно. Например ,в первом случае, можно отреагировать на min == max и просто написать ответ. Во втором случае ответ будет 100,5. Значит - вверху (пост 12) трохи исправила. И вроде выходит 100. Ищите багу дальше. Добавлено через 1 минуту Третий: 1 2 101 A = 1 B = 101 C = 51 1, 2 M = 2 Даёт два, как положено. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 01:51
	IrineK, 3 1 2 2. будет всегда приближаться к 2, но не достигнет. он все таки достиг 2, я проверил. повезло. математически он не должен достигнуть 2. а стоп. так он не остановится даже. всегда К будет равняться единице. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 02:01
	Значит, ограничим число итераций, скажем, n+1. И, если не удалось найти, мутим обратный ход - работаем во второй половине от максимума до середины. A = 1 B = 2 C = 1.5 ищем те элементы, что больше, и минимальный из них 2, 2 М = 2 - это ответ 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 02:12
	IrineK, кажись тут не работает теперь 5 1 1 2 2 3 1)A == 1, B == 3, C == 2, K == 2; 2)A == 2, B == 3, C == 2.5, K == 4, 3)A == 2, B == 2.5, C == 2.25, K == 4 ..... n + 1) A == 2, B == 2, K == 2. не нашлось. мутим обратно. 1)A == 1, B == 3, C == 2, K == 1; 2)A == 1, B == 2, C == 1.5, K == 4 3)A == 1.5, B == 2 C == 1.75, K == 4 и тут он опять приближается к двойке, только с другой стороны и K всегда равно 4, и в конце 1. опять ничего не найдено. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 02:30
	2n+1 = 5 1 1 2 2 3 A = 1 B = 3 C = 2 1,1,2,2 M = 2 A = 1 B = 2 C = 1.5 1,1 M = 1 cycled... A = 1 B = 3 C = 2 2,2,3 M = 2 - END Еще подрихтовала - ищем числа не строго меньше, а меньше-равно (от минимума до середины) или больше-равно (от середины до максимума). Добавлено через 5 минут 2N+1 = 19 N = 9 1 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 A = 1 B = 5 C = 3 1,3 M = 3 A = 3 B = 5 C = 4 1,3,4,4,4,4,4,4,4,4 M = 4 - здесь нужно еще среагировать на перебор за счет одинаковых элементов, т.к. по идее - здесь должен быть останов. SlavaSSU, у вас код уже есть? ) 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.12.2014, 02:31
	IrineK, яне писал. но могу накатать, то что первым ответил ТСу. 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	30.12.2014, 02:33
	Поздно уже. Продолжим завтра ) 0