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

@Дарья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

Поздно уже.

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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Как найти медиану неотсортированного массива (без использования дополнительного массива) 29.12.2014, 23:59. Показов 20652. Ответов 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