Нахождение "середины" массива.

[zOdmin]

Не совсем по языку вопрос, скорее поиск алгоритма.

Возможно ли за O(N) найти число, которое было бы меньше ровно половины чисел из не отсортированного массива чисел, в котором четное количество элементов и никакие числа не равны?

Например, для массива [9,7,1,8] это число будет 7.5

[ksa]

из не отсортированного массива чисел

Что мешает отсортировать тот массив?

[danik.js]

Что мешает отсортировать тот массив?

Сложность алгоритма, большая чем O(N) ?

[zOdmin]

Да, с сортировкой всё слишком просто. Думал, может всё же можно как-то за O(N) успеть.

В общем, задача "немного" упрощается, потому что может быть удастся использовать информацию из других итераций основного цикла. Самое смешное, что это реальная задача, а не забавы ради.

Короче, находить это число нужно для большого количества массивов. Каждый следующий массив получается из предыдущего путем таких манипуляций: сначала прибавляем 1 к первому элементу, потом 2 ко второму и т.д. К последнему элементу добавляем N. Предположим, что самый первый массив мы таки отсортировали (за NlogN действий или встроенной функцией) и нашли "среднее" число. Поможет ли нам это в нахождении "среднего" числа следующего массива?

[mta88]

походу все-таки можно
я сам в шоке

нужен алгоритм BFPRT

алгоритм дает верхнуюю границу сложности поиска i-го порядкового элемента в массиве из n элементов следующего вида -- 103*n/18

в случае вашей задачи

• находим за линейное время элемент n/2
• находим за линейное время элемент n/2+1
• берем среднее арифметическое этих двух элементов

people.csail.mit.edu/rivest/pubs/BFPRT72.pdf -- вроде бы оригинал статьи об алгоритме
ru.wikipedia.org/wiki/BFPRT-Алгоритм -- версия в википедии

-----------------------------------------------------------------
P.S.
я протупил
описал как найти медиану
надо найти только элемент n/2 или n/2+1 в зависимости от направления сортировки

[mta88]

а с практической точки зрения я б не заморачивался такими оптимизациями
n*log n более чем достаточно

[zOdmin]

походу все-таки можно
я сам в шоке

нужен алгоритм BFPRT

Не подходит:
http://ru.wikipedia.org/wiki/BFPRT-Алгоритм

1. Список делится на подмножества элементов, по 5 элементов в каждом (кроме последнего подмножества). Число элементов в подмножествах может варьировать от 5 до 21 и должно быть в любом случае нечётным.
2. Каждое подмножество сортируется с помощью подходящего алгоритма сортировки.

а с практической точки зрения я б не заморачивался такими оптимизациями
n*log n более чем достаточно

Просто слишком много вычислений. В посте №4 я приблизился к сути реальной задачи. Сортировка внутри цикла выглядит не очень хорошо.

[рони]

найти число, которое было бы меньше ровно половины чисел из не отсортированного массива чисел, в котором четное количество элементов и никакие числа не равны?
Например, для массива [9,7,1,8] это число будет 7.5

Вариант ...

var arr = [9,7,1,8], a = [1, 2, 3, 4, 5, 6, 7, 8];
function get(arr)
{
  var  m = Math.max(arr[0],arr[1]) , n = Math.min(arr[0],arr[1]);
  for (var i=0; i<arr.length; i=i+2)  {
  var min = Math.min(arr[i],arr[i+1]),
  max = Math.max(arr[i],arr[i+1]);
  if (max < m) m = max;
  if (min > n) n = min;
} ;
  return (n+m)/2
}
alert([get(arr),get(a)].join('\n'));

[mta88]

не подходит

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

[danik.js]

рони,а теперь без встроенных функций )